$\text{Estudio Empírico del Problema de Alquiler de Canoas}$¶

Índice General:¶

    1. Introducción
    1. Enunciado del Problema
    • 2.1. Ejemplo de Instancia
    • 2.2. Justificación de los 3 Algoritmos
    1. Metodología y Diseño del Experimento
    • 3.1. Objetivos de Investigación
    • 3.2. Hipótesis
    • 3.3. Variables
    • 3.4. Tamaño de Instancias
    • 3.5. Plan de Ejecución
    • 3.6. Generación de Instancias
    • 3.7. Herramientas y Librerías
    1. Implementación en Python
    • 4.1. Funciones para Generar Instancias
    • 4.2. Algoritmos a Comparar
    • 4.3. Pruebas Unitarias
    • 4.4. Función Principal de Experimentos
    1. Análisis Estadístico y Validación de Hipótesis
    • 5.1. Estadística Descriptiva (psutil)
    • 5.2. Contraste de Hipótesis
      • 5.2.1. ANOVA
      • 5.2.2. Pruebas Post-hoc
      • 5.2.3. Prueba t-Test
    • 5.3. Estadística Descriptiva (tracemalloc)
    • 5.4. Contraste de Hipótesis
      • 5.4.1. ANOVA
      • 5.4.2. Pruebas Post-hoc
      • 5.4.3. Prueba t-Test
    1. Regresiones y Técnicas de Machine Learning
    1. Discusión de Resultados
    1. Conclusiones
    1. Reproducibilidad
    1. Ética de la Investigación
    1. Referencias Bibliográficas

1. Introducción¶

Este proyecto analiza empíricamente el Problema de Alquiler de Canoas, que consiste en alquilar canoas en distintos puertos a lo largo de un río y devolverlas río abajo, minimizando el costo total de viaje. Existen costos directos entre puertos que pueden no ser aditivos, lo cual motiva comparaciones entre tres enfoques algorítmicos fundamentales:

  • Fuerza Bruta Recursiva (exploración exhaustiva sin optimización).
  • Recursión con Memoización (optimización top-down con almacenamiento de subproblemas).
  • Programación Dinámica (solución iterativa bottom-up).

Para evaluar el rendimiento de estas soluciones se diseñará un experimento masivo con distintos tamaños de instancias (XS, S, M, L, XL) y varias réplicas, midiendo tiempo de ejecución y uso de memoria. Además, se contempla la ejecución en múltiples lenguajes de programación con posterior unificación de los datos, permitiendo así un análisis estadístico extenso, validación de hipótesis, y eventualmente modelado predictivo (regresiones, machine learning) del rendimiento.


2. Enunciado del Problema¶

  • Número de Puertos ($n$): Se enumeran de 1 a ($n$).
  • Matriz de Costos ($\text{costo}[i][j])$: Representa el costo de alquilar una canoa en el puerto ($i$) y devolverla en el puerto ($j$) (con $(i < j)$).
  • Observación: Es posible que viajar directamente $(i \to j)$ sea más costoso que fraccionar el viaje en varios tramos intermedios, por lo que la solución óptima podría involucrar paradas.
  • Objetivo: Minimizar el costo total desde un puerto inicial (usualmente 1) hasta un puerto final (usualmente ($n$)).

Nos interesa comparar distintos métodos para resolver el problema, considerando tiempo y memoria.


2.1 Ejemplo de Instancia¶

Supongamos que hay 5 puertos a lo largo del río, numerados del 1 al 5. Se tiene la siguiente matriz de costos de alquiler de canoas entre los puertos:

De / A 1 2 3 4 5
1 0 10 25 30 50
2 - 0 12 20 35
3 - - 0 8 15
4 - - - 0 5
5 - - - - 0

Donde el valor en la celda (i, j) representa el costo de alquilar una canoa desde el puerto i hasta el puerto j. Un guion - indica que no se puede viajar río arriba.

En este caso, aunque el costo de alquilar una canoa de 1 a 4 directamente es 30, podríamos notar que:

  • Ir de 1 a 3 cuesta 25.
  • Luego, tomar otra canoa de 3 a 4 cuesta 8. El costo total usando esta estrategia sería 25 + 8 = 33, que es mayor que el alquiler directo, por lo que no conviene.

Sin embargo, para viajar de 1 a 5, si se toma la ruta directa, el costo es 50, pero podemos evaluar otras opciones:

  • Ir de 1 a 3 (25) y luego de 3 a 5 (15) da un total de 40, que es más barato que el alquiler directo de 1 a 5 (50).
  • Ir de 1 a 2 (10), luego de 2 a 4 (20) y después de 4 a 5 (5) da un total de 10 + 20 + 5 = 35, que es aún más barato.

Así, el costo mínimo de 1 a 5 sería 35 usando la combinación óptima de alquileres.


2.2 Justificación de los 3 Algoritmos¶

  1. Fuerza Bruta Recursiva

    • Complejidad Temporal: $O(2^n)$ (exponencial).

    • Complejidad Espacial: $O(n)$ (profundidad de la pila de recursión).

    • Propósito: Sirve como línea base para entender el comportamiento del problema sin optimizaciones. Su naturaleza recursiva explora todas las rutas posibles mediante un árbol de decisiones, lo que lo hace inviable para $n > 20$.

  2. Recursión con Memoización

    • Complejidad Temporal: $O(n^2)$.

    • Complejidad Espacial: $O(n)$ (tabla de memoización $O(n)$ + pila de recursión $O(n)$).

    • Propósito: Demuestra cómo la memoización reduce drásticamente la complejidad al evitar recálculos. Es una optimización natural de la fuerza bruta recursiva.

  3. Programación Dinámica (Bottom-Up)

    • Complejidad Temporal: $O(n^2)$.

    • Complejidad Espacial: $O(n)$ (arreglo unidimensional para almacenar costos mínimos).

    • Propósito: Representa la solución más eficiente en términos de memoria y tiempo constante, al eliminar la sobrecarga de la recursión.


3. Metodología y Diseño del Experimento¶

3.1 Objetivos de Investigación¶

  • Comparar los tiempos de ejecución y uso de memoria de tres enfoques algorítmicos para el Problema de Alquiler de Canoas:

    • Fuerza Bruta Recursivo (equivalente a recursividad sin memoización).
    • Recursivo con Memoización.
    • Programación Dinámica (Bottom-Up).
  • Validar empíricamente las complejidades teóricas de estos métodos: exponencial $O(2^n)$ para el Fuerza Bruta Recursivo versus $O(n^2)$ para los métodos optimizados.

  • Probar estadísticamente si, para tamaños de instancia grandes, la Programación Dinámica y el Recursivo con Memoización superan significativamente a la Fuerza Bruta Recursivo.

  • Generar un dataset amplio (posiblemente con miles o decenas de miles de instancias) para un análisis avanzado (regresiones, machine learning).

  • Permitir la ejecución en C y Python, con posterior unificación de resultados.


3.2 Hipótesis¶

  1. (Hipótesis de Tiempo)
  • H0 (nula): No existe diferencia estadísticamente significativa en el tiempo de ejecución promedio de los tres algoritmos.

  • H1 (alternativa): La Programación Dinámica y el Recursivo con Memoización exhiben menor tiempo de ejecución promedio que la Fuerza Bruta Recursivo, especialmente cuando $n$ es mediano/grande.

  1. (Hipótesis de Memoria)
  • H0: No existe diferencia estadísticamente significativa en el uso de memoria entre el Recursivo con Memoización y la Programación Dinámica.

  • H1: El Recursivo con Memoización utiliza, en promedio, más memoria debido a la combinación de la pila de llamadas y la tabla de memoización.


3.3 Variables¶

  1. Variables Independientes:

    • Tamaño de instancia ( $ n $ ): Categorías XS, S, M, L, XL.
    • Algoritmo: {Fuerza Bruta Recursivo, Recursivo con Memoización, PD Bottom-Up}.
    • Tipo de instancia: {Aleatoria Uniforme, Aleatoria Estructurada}.
    • Réplicas: Número de repeticiones por combinación.
    • Lenguaje: Identificador del lenguaje de programación donde se ejecuta.
  2. Variables Dependientes:

    • Tiempo de ejecución (segundos, medido con time.perf_counter()).
    • Uso de memoria (MB, medido con memory_profiler).
    • Costo Mínimo (para verificar correctitud).

3.4 Tamaño de Instancias (XS, S, M, L, XL)¶

Propuesta:

  • XS: $n \in \{4, 5, 7, 10, 14\}$
  • S: $n \in \{15, 18, 20, 22, 24\}$
  • M: $n \in \{25, 30, 35, 40, 45\}$
  • L: $n \in \{50, 60, 70, 80, 90\}$
  • XL: $n \in \{100, 120, 150, 200, 400\}$

Omitir fuerza bruta recursivo en escalas muy altas si su tiempo es excesivo por ejemplo $n \leq 15$


3.5 Plan de Ejecución Paso a Paso¶

  1. Crear un diccionario que asocia cada categoría (XS, S, M, L, XL) con sus valores de $n$.
  2. Para cada $n$ de cada categoría:
    • Para cada tipo de instancia (Uniforme, Estructurada):
      • Generar la matriz de costos, usando semillas (para reproducibilidad).
      • Para cada algoritmo:
        • Medir tiempo y memoria.
        • Almacenar resultado en un DataFrame de pandas con columnas:
          • language_id, category_size, n, tipo_instancia, algoritmo, replica_id, tiempo_ejecucion, memoria_max_mb, costo_minimo y status.
  3. Repetir réplicas (p.ej. 50) para capturar variabilidad estadística.
  4. Guardar los datos en un CSV (o varios CSV) por lenguaje.
  5. Unir CSV de todas los lenguajes (2) en un único dataset para análisis conjunto.

3.6 Generación de Instancias¶

  • Aleatoria Uniforme: $ \text{costo}[i][j] \sim \text{Uniform}(1,10) \quad (\text{enteros}) $
  • Aleatoria Estructurada (pseudo-aditiva):
    1. Inicializar $\text{costo}[i][j]$ con valores en $[1,10]$.
    2. “Refinar” usando reglas aditivas:

\begin{equation} \begin{aligned} \text{costo}[i][j] &= \min \left\{ \text{costo}[i][j], \text{costo}[i][k] + \text{costo}[k][j] + \delta \right\} &\text{donde } \delta \in [-5,5] \end{aligned} \end{equation}


3.7 Herramientas y Librerías de Python¶

In [ ]:
# Gráficos, Datos y Cálculos
import numpy as np # Matrcies
import matplotlib.pyplot as plt # graficos
import seaborn as sns # Graficos elaborados
import plotly.express as px # Graficos interactivos
import matplotlib.ticker as ticker # configurar la localización y el formato de los ticks (marcas) en los ejes
import math # Para el manejo de infinito
import pandas as pd # Manejo de datasets
import json # manejos archivos complejos

# Programación en PARALELO
import os # Interacción con el sistema operativo
import psutil # Monitoreo de recursos del sistema
import tracemalloc # Seguimiento de uso de memoria
from joblib import Parallel, delayed # Ejecución paralela de tareas


# Gestión de Memoria y Tiempo t pruebas unitarias
import random  # Importa el módulo random para generar números aleatorios
import unittest # Para pruebas unitarias (Framework)
import time # Para medir el tiempo


# Estadística
import statsmodels.api as sm # Módulo principal de statsmodels para realizar análisis estadísticos como regresión, modelos lineales, pruebas estadísticas, etc.
from statsmodels.formula.api import ols # Para ajustar modelos de regresión lineal usando fórmulas estilo R
from statsmodels.stats.multicomp import pairwise_tukeyhsd # realizar la prueba de comparaciones múltiples de Tukey entre grupos.
from scipy.stats import ttest_ind # Para realizar la prueba t de Student para comparar dos muestras independientes.


# Machine Learning
from sklearn.preprocessing import OneHotEncoder # Variables categóricas
from sklearn.preprocessing import StandardScaler # Escalamiento de datos
from sklearn.model_selection import train_test_split # Data splitting
from sklearn.ensemble import RandomForestRegressor # modelo de regresión de bosque aleatorio, que utiliza múltiples árboles de decisión para hacer predicciones
from sklearn.ensemble import RandomForestClassifier # modelo de clasificación de bosque aleatorio
from sklearn.metrics import mean_absolute_error, r2_score, classification_report, accuracy_score  # Métricas de evaluación
In [ ]:
from google.colab import drive # Conectarse al drive, para cargar los archivos json generados
drive.mount('/content/drive')
Mounted at /content/drive

4. Implementación en Python:¶

4.1 Funciones para Generar Instancias¶

Instancias uniforme y estructurada.¶

In [ ]:
def generar_instancia_uniforme(n, low=1, high=10, seed=None):
    """
    Genera una matriz de costos de dimensiones (n+1) x (n+1).
    Para cada par (i, j) con i < j, asigna un valor entero aleatorio en el rango [low, high].
    """
    if seed is not None:               # Verifica si se ha proporcionado una semilla para la aleatoriedad
        random.seed(seed)              # Si es así, establece la semilla para garantizar reproducibilidad
    # Crea una matriz (lista de listas) de tamaño (n+1) x (n+1) inicializada en 0
    costo = [[0] * (n+1) for _ in range(n+1)]
    # Itera sobre los índices de fila desde 1 hasta n-1 (se omite la fila 0)
    for i in range(1, n):
        # Para cada fila i, itera sobre los índices de columna desde i+1 hasta n
        for j in range(i+1, n+1):
            # Asigna un costo aleatorio entero entre low y high al par (i, j)
            costo[i][j] = random.randint(low, high)
    return costo

def generar_instancia_estructurada(n, low=1, high=10, seed=None):
    """
    Genera una matriz de costos pseudo-aditiva con dos fases:
    1) Inicialización: Se asigna un valor entero aleatorio en [low, high] para cada par (i, j) con i < j.
    2) Refinamiento: Se ajustan los costos considerando rutas indirectas y añadiendo un delta aleatorio en [-5, 5].
    """
    if seed is not None:
        random.seed(seed)

    costo = [[0] * (n+1) for _ in range(n+1)]

    # Paso 1: Inicialización básica de la matriz de costos
    for i in range(1, n):
        for j in range(i+1, n+1):     # Itera para cada puerto j que es mayor que i
            # Asigna un costo aleatorio entero entre low y high al tramo directo (i, j)
            costo[i][j] = random.randint(low, high)

    # Paso 2: Refinamiento de la matriz para introducir pseudo-aditividad
    for i in range(1, n):
        for j in range(i+2, n+1):# Para cada origen i, itera sobre destinos j donde existe al menos un puerto intermedio
            for k in range(i+1, j):   # Itera sobre todos los posibles puertos intermedios entre i y j
                # Genera un delta aleatorio entero en el rango [-25, 25]
                delta = random.randint(-5, 5)
                # Calcula el costo posible de la ruta indirecta pasando por k
                posible = costo[i][k] + costo[k][j] + delta
                # Si el costo indirecto es menor que el costo directo actual, se actualiza
                if posible < costo[i][j]:
                    # Se asegura que el costo actualizado no sea menor que 1
                    costo[i][j] = max(1, posible)
    return costo
In [ ]:
def generar_instancias_globales(categories_dict, tipos_instancia, num_replicas, seed_list):
    """
    Genera todas las instancias de costos de antemano, asociadas a semillas únicas.

    Retorna:
        list: Lista de diccionarios con estructura:
            {
                'category': str,
                'n': int,
                'tipo_instancia': str,
                'replica_id': int,
                'seed': int,
                'costo': list(list(int))
            }
    """
    instancias = []
    exp_counter = 0

    for category_name, list_n in categories_dict.items():
        for n in list_n:
            for tipo in tipos_instancia:
                for r in range(num_replicas):
                    seed = seed_list[exp_counter % len(seed_list)]
                    exp_counter += 1

                    if tipo == "uniforme":
                        costo = generar_instancia_uniforme(n, seed=seed)
                    elif tipo == "estructurada":
                        costo = generar_instancia_estructurada(n, seed=seed)
                    else:
                        raise ValueError("Tipo de instancia no válido.")

                    instancias.append({
                        'category': category_name,
                        'n': n,
                        'tipo_instancia': tipo,
                        'replica_id': r,
                        'seed': seed,
                        'costo': costo
                    })
    return instancias

Instancias en PARALELO¶

In [ ]:
import numpy as np
import random
import json
from joblib import Parallel, delayed

def generar_instancia_uniforme(n, low=1, high=10, seed=None):
    """
    Genera una matriz de costos (n+1)x(n+1) para la instancia "uniforme".
    Para cada par (i, j) con i >= 1 y j > i se asigna un valor aleatorio entero en [low, high].
    Se utiliza vectorización con NumPy para mayor rendimiento.
    """
    if seed is not None:
        np.random.seed(seed)
    # Crear una matriz de ceros
    costo = np.zeros((n+1, n+1), dtype=int)
    # Obtener los índices del triángulo superior (excluyendo la fila 0)
    rows, cols = np.triu_indices(n+1, k=1)
    mask = rows >= 1  # ignorar la fila 0
    rows, cols = rows[mask], cols[mask]
    # Asignar valores aleatorios a los elementos de la parte superior
    costo[rows, cols] = np.random.randint(low, high + 1, size=len(rows))
    return costo.tolist()

def generar_instancia_estructurada(n, low=1, high=10, seed=None):
    """
    Genera una matriz de costos (n+1)x(n+1) para la instancia "estructurada".
    Se procede en dos fases:
      1. Inicialización: se asigna un valor aleatorio entero en [low, high] a cada par (i, j) con i>=1 y j>i.
      2. Refinamiento: para cada par (i,j) se exploran rutas indirectas (pasando por un k intermedio)
         y se ajusta el costo si se encuentra una ruta más barata, sumándole un delta aleatorio en [-5, 5].
    La inicialización se vectoriza, pero el refinamiento se realiza con bucles.
    """
    if seed is not None:
        np.random.seed(seed)
    costo = np.zeros((n+1, n+1), dtype=int)
    # Fase 1: Inicialización vectorizada (ignorar la fila 0)
    rows, cols = np.triu_indices(n+1, k=1)
    mask = rows >= 1
    rows, cols = rows[mask], cols[mask]
    costo[rows, cols] = np.random.randint(low, high + 1, size=len(rows))

    # Fase 2: Refinamiento (exploración de rutas indirectas)
    for i in range(1, n):
        for j in range(i+2, n+1):
            for k in range(i+1, j):
                # delta aleatorio entre -5 y 5 (incluidos)
                delta = np.random.randint(-5, 6)
                posible = costo[i][k] + costo[k][j] + delta
                if posible < costo[i][j]:
                    costo[i][j] = max(1, posible)
    return costo.tolist()

def generar_instancias_por_combinacion(category_name, n, tipo, num_replicas, seed_list):
    """
    Genera todas las réplicas para una combinación de (categoría, n, tipo de instancia).
    Se itera internamente sobre el número de réplicas, asignando una semilla de la lista.
    """
    instancias = []
    for replica in range(num_replicas):
        # Selecciona una semilla cíclicamente de seed_list
        seed = seed_list[replica % len(seed_list)]
        if tipo == "uniforme":
            costo = generar_instancia_uniforme(n, seed=seed)
        elif tipo == "estructurada":
            costo = generar_instancia_estructurada(n, seed=seed)
        else:
            raise ValueError("Tipo de instancia no válido: {}".format(tipo))
        instancias.append({
            'category': category_name,
            'n': n,
            'tipo_instancia': tipo,
            'replica_id': replica,
            'seed': seed,
            'costo': costo
        })
    return instancias

def generar_instancias_globales_parallel(categories_dict, tipos_instancia, num_replicas, seed_list):
    """
    Genera todas las instancias de forma paralela agrupando por cada combinación de:
      - Categoría (clave en categories_dict)
      - Tamaño n (valor en la lista asociada a la categoría)
      - Tipo de instancia (por ejemplo, 'uniforme' o 'estructurada')

    Se utiliza joblib.Parallel para distribuir la generación de las réplicas de cada combinación.
    """
    tasks = []
    for category_name, list_n in categories_dict.items():
        for n in list_n:
            for tipo in tipos_instancia:
                tasks.append((category_name, n, tipo))

    # Paralelizar sobre cada combinación (reduciendo la sobrecarga al evitar tareas muy pequeñas)
    resultados = Parallel(n_jobs=-1)(
        delayed(generar_instancias_por_combinacion)(cat, n, tipo, num_replicas, seed_list)
        for (cat, n, tipo) in tasks
    )

    # Aplanar la lista de listas en una sola lista de instancias
    instancias = [inst for sublist in resultados for inst in sublist]
    return instancias

if __name__ == '__main__':
    # Parámetros de ejemplo
    CATEGORIES = {
        "XS": [4, 5, 7, 10, 14],
        "S": [15, 18, 20, 22, 24],
        "M": [25, 30, 35, 40, 45],
        "L": [50, 60, 70, 80, 90],
        "XL": [100, 120, 150, 200, 400]
    }
    tipos_instancia = ['uniforme', 'estructurada']
    num_replicas = 50
    # Generar una lista de semillas aleatorias
    seed_list = [random.randint(0, 999999) for _ in range(100)]

    # Generar todas las instancias en paralelo
    instancias = generar_instancias_globales_parallel(CATEGORIES, tipos_instancia, num_replicas, seed_list)

    # Guardar el resultado en un archivo JSON
    with open('instancias_parallel.json', 'w') as f:
        json.dump(instancias, f, default=str)

    print("Instancias guardadas en 'instancias_parallel.json'")
Instancias guardadas en 'instancias_parallel.json'

4.2 Algoritmos a Comparar¶

In [ ]:
def fuerza_bruta_recursivo(costo, i, n):
    """
    Implementa la estrategia recursiva sin memoización para el Problema de Alquiler de Canoas.
    Explora todas las rutas posibles de manera exhaustiva.
    Parámetros:
      - costo: matriz de costos (dimensiones (n+1) x (n+1)), donde costo[i][j] es el costo de ir del puerto i al j.
      - i: puerto de origen actual.
      - n: número total de puertos.

    Retorna:
      - Costo mínimo acumulado desde el puerto i hasta el puerto n.
    """
    if i >= n: # Maneja i > n (casos con 0 o 1 puerto) ✅
        return 0  # Caso base: si se llega al último puerto, no se requiere costo adicional.
    min_cost = math.inf  # Inicializa el costo mínimo con infinito.
    for j in range(i+1, n+1):  # Explora todos los puertos siguientes (i+1 a n).
        actual = costo[i][j] + fuerza_bruta_recursivo(costo, j, n)
        if actual < min_cost:
            min_cost = actual
    return min_cost

def recursivo_con_memo(costo, i, n, memo):
    """
    Variante optimizada de la recursión que almacena resultados intermedios para evitar recomputaciones.

    Parámetros:
      - costo: matriz de costos.
      - i: puerto de origen actual.
      - n: número total de puertos.
      - memo: lista de tamaño (n+1) para almacenar el costo mínimo ya calculado para cada puerto.

    Retorna:
      - Costo mínimo acumulado desde el puerto i hasta el puerto n.
    """
    if i >= n:  # Caso base. Pero Maneja i >= n (casos con 0 o 1 puerto) ✅
        return 0
    if memo[i] is not None:
        return memo[i]  # Retorna el resultado ya calculado para el puerto i.
    min_cost = math.inf
    for j in range(i+1, n+1):
        actual = costo[i][j] + recursivo_con_memo(costo, j, n, memo)
        if actual < min_cost:
            min_cost = actual
    memo[i] = min_cost  # Guarda el resultado para el puerto i.
    return min_cost

def recursivo_con_memo_wrapper(costo, n):
    """
    Inicializa la tabla de memoización y llama a la función recursiva optimizada.

    Parámetros:
      - costo: matriz de costos.
      - n: número total de puertos.

    Retorna:
      - Costo mínimo desde el puerto 1 hasta el puerto n.
    """
    if n == 0:  # Caso especial: no hay puertos destino ✅
        return 0
    memo = [None] * (n+1)  # Crea una lista para almacenar resultados de subproblemas.
    return recursivo_con_memo(costo, 1, n, memo)

def programacion_dinamica(costo, n):
    """
    Resuelve el problema de forma iterativa, comenzando desde el último puerto hasta el primero.

    Parámetros:
      - costo: matriz de costos.
      - n: número total de puertos.

    Retorna:
      - Costo mínimo desde el puerto 1 hasta el puerto n.
    """
    if n == 0:  # Caso especial: no hay puertos destino ✅
        return 0
    dp = [0] * (n+1)
    dp[n] = 0  # Caso base: costo 0 al llegar al último puerto.
    for i in range(n-1, 0, -1):  # Itera desde n-1 hasta 1.
        dp[i] = math.inf  # Inicializa con infinito.
        for j in range(i+1, n+1):
            actual = costo[i][j] + dp[j]
            if actual < dp[i]:
                dp[i] = actual
    return dp[1]

4.3 Pruebas Unitarias¶

In [72]:
class TestAlgoritmosCanoas(unittest.TestCase):
    """
    Conjunto exhaustivo de pruebas unitarias para los algoritmos del Problema de Alquiler de Canoas.
    Cubre casos bordes, mínimos, estructurados y no estructurados, validando correctitud y robustez.
    """

    # --------------------------
    # Casos Bordes y Mínimos
    # --------------------------
    def test_n0_0_puertos(self):
        """Caso borde: 0 puertos destino (solo el inicial)."""
        costo = [[0]]  # Matriz 1x1 (n=0)
        n = 0
        self._ejecutar_pruebas(costo, n, 0)

    def test_n1_1_puerto(self):
        """Caso borde: 1 puerto (inicio = fin)."""
        costo = [[0, 0],
                [0, 0]]  # Matriz 2x2 (n=1)
        n = 1
        self._ejecutar_pruebas(costo, n, 0)

    def test_n2_2_puertos(self):
        """Caso mínimo no trivial: 2 puertos (ruta directa única)."""
        costo = [
            [0, 0, 0],
            [0, 0, 5],  # 1→2
            [0, 0, 0]
        ]
        n = 2
        self._ejecutar_pruebas(costo, n, 5)

    # --------------------------
    # Casos con Estructura Aditiva
    # --------------------------
    def test_n3_ruta_optima_no_directa(self):
        """Ruta óptima requiere múltiples saltos (1→2→3)."""
        costo = [
            [0, 0, 0, 0],
            [0, 0, 2, 10],  # 1→3=10
            [0, 0, 0, 3],   # 2→3=3
            [0, 0, 0, 0]
        ]
        n = 3
        self._ejecutar_pruebas(costo, n, 5)  # 2+3=5

    def test_n4_ruta_optima_multiple_saltos(self):
        """Caso clásico con 4 puertos y ruta óptima en 3 saltos (1→2→3→4)."""
        costo = [
            [0, 0, 0, 0, 0],
            [0, 0, 2, 5, 9],  # 1→4=9
            [0, 0, 0, 2, 4],  # 2→4=4
            [0, 0, 0, 0, 2],  # 3→4=2
            [0, 0, 0, 0, 0]
        ]
        n = 4
        self._ejecutar_pruebas(costo, n, 6)  # 2+2+2=6

    # --------------------------
    # Casos con Estructura Pseudo-Aditiva
    # --------------------------
    def test_n4_estructura_pseudo_aditiva(self):
        """Costo mínimo con 'delta negativo' simulado (1→2→3→4 = 1+1+1=3)."""
        costo = [
            [0, 0, 0, 0, 0],
            [0, 0, 1, 5, 10],  # 1→4=10
            [0, 0, 0, 1, 3],   # 2→4=3
            [0, 0, 0, 0, 1],   # 3→4=1
            [0, 0, 0, 0, 0]
        ]
        n = 4
        self._ejecutar_pruebas(costo, n, 3)

    # --------------------------
    # Casos con Rutas Directas Óptimas
    # --------------------------
    def test_n3_ruta_directa_optima(self):
        """Camino directo es óptimo (1→3=15 vs 1→2→3=20)."""
        costo = [
            [0, 0, 0, 0],
            [0, 0, 10, 15],  # 1→3=15
            [0, 0, 0, 10],   # 2→3=10
            [0, 0, 0, 0]
        ]
        n = 3
        self._ejecutar_pruebas(costo, n, 15)

    # --------------------------
    # Casos de Mayor Escala (Stress)
    # --------------------------
    def test_n5_complejidad_creciente(self):
        """Caso con 5 puertos y estructura jerárquica."""
        costo = [
            [0, 0, 0, 0, 0, 0],
            [0, 0, 2, 5, 9, 20],  # 1→5=20
            [0, 0, 0, 2, 4, 7],   # 2→5=7
            [0, 0, 0, 0, 2, 5],   # 3→5=5
            [0, 0, 0, 0, 0, 3],   # 4→5=3
            [0, 0, 0, 0, 0, 0]
        ]
        n = 5
        self._ejecutar_pruebas(costo, n, 9)  # 1→2→3→4→5 = 2+2+2+3=9 ❌ ¿Error? ¡Validar!

    # --------------------------
    # Método Auxiliar
    # --------------------------
    def _ejecutar_pruebas(self, costo, n, expected):
        """Ejecuta los tres algoritmos y verifica el resultado esperado."""
        # Fuerza Bruta Recursivo
        result_fb = fuerza_bruta_recursivo(costo, 1, n)
        self.assertEqual(result_fb, expected, f"Fuerza Bruta falló: {result_fb} != {expected}")

        # Recursivo con Memoización
        result_memo = recursivo_con_memo_wrapper(costo, n)
        self.assertEqual(result_memo, expected, f"Memoización falló: {result_memo} != {expected}")

        # Programación Dinámica
        result_dp = programacion_dinamica(costo, n)
        self.assertEqual(result_dp, expected, f"Programación Dinámica falló: {result_dp} != {expected}")

if __name__ == '__main__':
    unittest.main(argv=[''], exit=False)
........
----------------------------------------------------------------------
Ran 8 tests in 0.008s

OK

La solución propuesta es correcta, ya que al modificar la condición de parada a if i >= n: return 0, se garantiza el manejo seguro de casos borde (cuando $n \leq 1$). Esto evita el acceso a índices fuera del rango en la matriz de costos, retornando 0 en situaciones donde no existe un trayecto válido, y asegurando así la robustez de la función en escenarios de entrada mínima.

4.4 Función Principal de Experimentos¶

Creación (lectura) Json de instancias:¶

In [ ]:
# Se utiliza el módulo json para preservar la estructura original de lista de diccionarios.
# Y se importa con la previa ejecución de la función generar_instancias_globales

with open('/content/drive/MyDrive/UNAL/Semestre IV/Análisis y diseño de Algoritmos/Proyecto/instancias_50.json', 'r') as f:
    instancias = json.load(f)

Funciones auxiliares:¶

In [ ]:
# Para que se compatible con la programación en paralelo, ya que no admite el lambda
def fuerza_bruta_rec_func(costo, n):
    return fuerza_bruta_recursivo(costo, 1, n)
In [ ]:
# Los tres algoritmos a usar en el gran for incluyendo fuerza_bruta_rec_func

ALG_FUNC = {
    'fuerza_bruta_rec': fuerza_bruta_rec_func,
    'rec_con_memo': recursivo_con_memo_wrapper,
    'prog_dinamica': programacion_dinamica
}
In [ ]:
# Función que mide la memoria de programación en paralelo con

def medir_memoria():
    """
    Retorna el uso de memoria (RSS) del proceso actual en MB.
    """
    process = psutil.Process(os.getpid())
    mem_bytes = process.memory_info().rss
    return mem_bytes / (1024 * 1024)

Función que ejcuta todas las instancias con joblib¶

Experimentos usando psutil para memoria¶

In [ ]:
def ejecutar_experimento(instancia, algoritmos, skip_large_for_exponential=True):
    resultados = []
    category_name = instancia['category']
    n = instancia['n']
    tipo = instancia['tipo_instancia']
    r = instancia['replica_id']
    costo = instancia['costo']

    for alg_name, alg_func in algoritmos.items():
        # Salta el algoritmo costoso si la instancia es grande
        if skip_large_for_exponential and alg_name in ["fuerza_bruta_rec"] and n >= 15:
            resultados.append({
                'language': "Python",
                'category_size': category_name,
                'n': n,
                'tipo_instancia': tipo,
                'algoritmo': alg_name,
                'replica_id': r,
                'tiempo_ejecucion': None,
                'memoria_max_mb': None,
                'costo_minimo': None,
                'status': "skipped_due_to_large_n"
            })
            continue

        mem_inicial = medir_memoria()
        t0 = time.perf_counter_ns()
        resultado = alg_func(costo, n)
        t1 = time.perf_counter_ns()
        mem_final = medir_memoria()

        tiempo = t1 - t0
        # Calculamos la diferencia de memoria entre el inicio y el fin
        mem_peak = mem_final - mem_inicial if mem_final >= mem_inicial else 0.0

        resultados.append({
            'language': "Python",
            'category_size': category_name,
            'n': n,
            'tipo_instancia': tipo,
            'algoritmo': alg_name,
            'replica_id': r,
            'tiempo_ejecucion': tiempo,
            'memoria_max_mb': mem_peak,
            'costo_minimo': resultado,
            'status': "ok"
        })
    return resultados

t1 = time.perf_counter_ns()

if __name__ == '__main__':
    # Ejecutar los experimentos en paralelo utilizando el backend "multiprocessing"
    all_results_paralelos = Parallel(n_jobs=-1, backend="multiprocessing")(
        delayed(ejecutar_experimento)(instancia, ALG_FUNC) for instancia in instancias
    )

    # Aplanar la lista de listas en una única lista de resultados:
    # Cada llamada a ejecutar_experimento retorna una lista de diccionarios y all_results_paralelos es una lista de estas listas.
    all_results = [resultado for sublista in all_results_paralelos for resultado in sublista]

    # Convertir la lista de diccionarios en un DataFrame para facilitar el análisis y almacenamiento
    df_resultados = pd.DataFrame(all_results)

    # Guardar el DataFrame en un archivo CSV
    df_resultados.to_csv("resultados_optimizados.csv", index=False)
    print("Resultados guardados en 'resultados_optimizados.csv'")

t2 = time.perf_counter_ns()
print(f"Tiempo de ejecución: {(t2 - t1) / 1e9} segundos")

Experimentos usando tracemalloc para memoria¶

In [ ]:
def ejecutar_experimento2(instancia, algoritmos, skip_large_for_exponential=True):
    resultados = []
    category_name = instancia['category']
    n = instancia['n']
    tipo = instancia['tipo_instancia']
    r = instancia['replica_id']
    costo = instancia['costo']

    for alg_name, alg_func in algoritmos.items():
        # Salta el algoritmo costoso si la instancia es grande
        if skip_large_for_exponential and alg_name in ["fuerza_bruta_rec"] and n >= 15:
            resultados.append({
                'language': "Python",
                'category_size': category_name,
                'n': n,
                'tipo_instancia': tipo,
                'algoritmo': alg_name,
                'replica_id': r,
                'tiempo_ejecucion': None,
                'memoria_max_mb': None,
                'costo_minimo': None,
                'status': "skipped_due_to_large_n"
            })
            continue

        # Inicia tracemalloc para rastrear asignaciones de memoria
        tracemalloc.start()
        t0 = time.perf_counter_ns()
        resultado = alg_func(costo, n)
        t1 = time.perf_counter_ns()
        # Obtiene la memoria actual y el pico durante la ejecución
        current, peak = tracemalloc.get_traced_memory()
        tracemalloc.stop()

        tiempo = t1 - t0
        # Convertir el pico de memoria de bytes a MB
        mem_peak_mb = peak / (1024 * 1024)

        resultados.append({
            'language': "Python",
            'category_size': category_name,
            'n': n,
            'tipo_instancia': tipo,
            'algoritmo': alg_name,
            'replica_id': r,
            'tiempo_ejecucion': tiempo,
            'memoria_max_mb': mem_peak_mb,
            'costo_minimo': resultado,
            'status': "ok"
        })
    return resultados

ti = time.perf_counter_ns()

if __name__ == '__main__':
    # Ejecutar los experimentos en paralelo utilizando todos los núcleos disponibles
    # Forzamos el backend "multiprocessing" para mayor compatibilidad
    all_results_paralelos = Parallel(n_jobs=-1, backend="multiprocessing")(
        delayed(ejecutar_experimento2)(instancia, ALG_FUNC) for instancia in instancias
    )

    # Aplanar la lista de listas en una única lista de resultados:
    # Cada llamada a ejecutar_experimento retorna una lista de diccionarios (uno por algoritmo)
    all_results = [resultado for sublista in all_results_paralelos for resultado in sublista]

    # Convertir la lista de diccionarios en un DataFrame para análisis y almacenamiento
    df_resultados = pd.DataFrame(all_results)

    # Guardar el DataFrame en un archivo CSV
    df_resultados.to_csv("resultados_optimizados2.csv", index=False)
    print("Resultados guardados en 'resultados_optimizados2.csv'")

tf = time.perf_counter_ns()
print(f"Tiempo de ejecución: {(tf - ti) / 1e9} segundos")

5. Análisis Estadístico y Validación de Hipótesis¶

**5.1 Estadística Descriptiva usando **psutil****¶

In [ ]:
# El archivo "resultados_optimizados.csv" es el más grande usado convertido
# del json de 80 MB con 50 réplicas en todos los tamaño y cargamos el usó:
# psutil, para medir memoria, sin embargo veamos las diferencias:

df = pd.read_csv("resultados_optimizados.csv")

df.head() # primeras 5 filas del dataset
Out[ ]:
language category_size n tipo_instancia algoritmo replica_id tiempo_ejecucion memoria_max_mb costo_minimo status
0 Python XS 4 uniforme fuerza_bruta_rec 0 48840.0 0.0 8.0 ok
1 Python XS 4 uniforme rec_con_memo 0 31924.0 0.0 8.0 ok
2 Python XS 4 uniforme prog_dinamica 0 19215.0 0.0 8.0 ok
3 Python XS 4 uniforme fuerza_bruta_rec 1 48948.0 0.0 5.0 ok
4 Python XS 4 uniforme rec_con_memo 1 28295.0 0.0 5.0 ok
In [ ]:
df['status'].value_counts() # cuántos experimentos no pasaron por ser fuerza_bruta_recursiva
Out[ ]:
count
status
ok 5500
skipped_due_to_large_n 2000

In [ ]:
df['memoria_max_mb'].value_counts() # contar los valores almacenados en la memoria
Out[ ]:
count
memoria_max_mb
0.000359 207
0.000214 200
0.000252 130
0.000519 102
0.001320 101
... ...
0.001747 1
0.001213 1
0.002815 1
0.002014 1
0.000946 1

69 rows × 1 columns


In [ ]:
df.info() # Información de los valores nulos
<class 'pandas.core.frame.DataFrame'>
RangeIndex: 7500 entries, 0 to 7499
Data columns (total 10 columns):
 #   Column            Non-Null Count  Dtype  
---  ------            --------------  -----  
 0   language          7500 non-null   object 
 1   category_size     7500 non-null   object 
 2   n                 7500 non-null   int64  
 3   tipo_instancia    7500 non-null   object 
 4   algoritmo         7500 non-null   object 
 5   replica_id        7500 non-null   int64  
 6   tiempo_ejecucion  5500 non-null   float64
 7   memoria_max_mb    5500 non-null   float64
 8   costo_minimo      5500 non-null   float64
 9   status            7500 non-null   object 
dtypes: float64(3), int64(2), object(5)
memory usage: 586.1+ KB
In [ ]:
# Filtrar filas skip para quedarse solo con los valores no null

df_ok = df[df['status'] == 'ok']

df_ok.head()
Out[ ]:
language category_size n tipo_instancia algoritmo replica_id tiempo_ejecucion memoria_max_mb costo_minimo status
0 Python XS 4 uniforme fuerza_bruta_rec 0 48840.0 0.0 8.0 ok
1 Python XS 4 uniforme rec_con_memo 0 31924.0 0.0 8.0 ok
2 Python XS 4 uniforme prog_dinamica 0 19215.0 0.0 8.0 ok
3 Python XS 4 uniforme fuerza_bruta_rec 1 48948.0 0.0 5.0 ok
4 Python XS 4 uniforme rec_con_memo 1 28295.0 0.0 5.0 ok
In [ ]:
df_ok.info() # Para observar los valores no null
<class 'pandas.core.frame.DataFrame'>
Index: 5500 entries, 0 to 7499
Data columns (total 10 columns):
 #   Column            Non-Null Count  Dtype  
---  ------            --------------  -----  
 0   language          5500 non-null   object 
 1   category_size     5500 non-null   object 
 2   n                 5500 non-null   int64  
 3   tipo_instancia    5500 non-null   object 
 4   algoritmo         5500 non-null   object 
 5   replica_id        5500 non-null   int64  
 6   tiempo_ejecucion  5500 non-null   float64
 7   memoria_max_mb    5500 non-null   float64
 8   costo_minimo      5500 non-null   float64
 9   status            5500 non-null   object 
dtypes: float64(3), int64(2), object(5)
memory usage: 472.7+ KB
In [ ]:
# 1) Descripción general en TIEMPO

desc_tiempos = df_ok.groupby(['n','algoritmo'])['tiempo_ejecucion'].describe()
print(desc_tiempos)
                      count         mean           std         min  \
n   algoritmo                                                        
4   fuerza_bruta_rec  100.0     61704.53  5.219786e+05      5507.0   
    prog_dinamica     100.0      8333.15  6.414380e+03      4822.0   
    rec_con_memo      100.0      9252.39  6.323947e+03      4969.0   
5   fuerza_bruta_rec  100.0     71704.46  6.040627e+05      7719.0   
    prog_dinamica     100.0      7446.58  2.076783e+03      4761.0   
    rec_con_memo      100.0      9050.13  3.311368e+03      5598.0   
7   fuerza_bruta_rec  100.0     89655.76  3.679048e+05     23834.0   
    prog_dinamica     100.0     10246.46  4.539836e+03      6740.0   
    rec_con_memo      100.0     12467.79  2.885704e+03      8355.0   
10  fuerza_bruta_rec  100.0    599048.61  1.808224e+06    175242.0   
    prog_dinamica     100.0     14550.88  7.014820e+03     10125.0   
    rec_con_memo      100.0    123796.30  1.046334e+06     13691.0   
14  fuerza_bruta_rec  100.0   9057766.59  4.656391e+06   3327855.0   
    prog_dinamica     100.0     43125.05  2.022890e+05     16718.0   
    rec_con_memo      100.0     93367.33  4.079445e+05     25983.0   
15  prog_dinamica     100.0    126053.13  1.004272e+06     19106.0   
    rec_con_memo      100.0     40318.71  1.251392e+04     30638.0   
18  prog_dinamica     100.0     89232.20  3.298731e+05     24041.0   
    rec_con_memo      100.0     57819.33  3.208278e+04     42961.0   
20  prog_dinamica     100.0    123894.15  5.608442e+05     27859.0   
    rec_con_memo      100.0    459493.91  2.336477e+06     52514.0   
22  prog_dinamica     100.0    427687.16  2.134244e+06     36750.0   
    rec_con_memo      100.0    694744.09  2.778932e+06     63002.0   
24  prog_dinamica     100.0    410099.93  1.520223e+06     38795.0   
    rec_con_memo      100.0    275771.42  7.922631e+05     72982.0   
25  prog_dinamica     100.0    192688.12  6.400553e+05     46350.0   
    rec_con_memo      100.0    655389.19  1.633963e+06     69245.0   
30  prog_dinamica     100.0    242661.98  9.610361e+05     66110.0   
    rec_con_memo      100.0    882480.41  2.536709e+06    118015.0   
35  prog_dinamica     100.0    409636.27  1.731741e+06     74558.0   
    rec_con_memo      100.0    607265.15  1.722300e+06    146013.0   
40  prog_dinamica     100.0    445079.86  1.542429e+06     89280.0   
    rec_con_memo      100.0   1500023.71  2.922949e+06    194345.0   
45  prog_dinamica     100.0   1097216.13  3.287741e+06    109536.0   
    rec_con_memo      100.0   1244409.70  2.954315e+06    210243.0   
50  prog_dinamica     100.0    586384.54  1.797410e+06    151026.0   
    rec_con_memo      100.0    826856.70  1.301032e+06    303578.0   
60  prog_dinamica     100.0    392000.90  8.465907e+05    180488.0   
    rec_con_memo      100.0    831116.31  1.249806e+06    443455.0   
70  prog_dinamica     100.0    524833.23  8.663803e+05    247990.0   
    rec_con_memo      100.0   1942961.03  1.993512e+06    709918.0   
80  prog_dinamica     100.0   1205857.18  2.358562e+06    329100.0   
    rec_con_memo      100.0   4043713.56  4.991925e+06   1008685.0   
90  prog_dinamica     100.0    948280.36  1.405468e+06    396132.0   
    rec_con_memo      100.0   3889019.50  4.498740e+06   1238241.0   
100 prog_dinamica     100.0   2155701.88  3.985881e+06    577108.0   
    rec_con_memo      100.0   6713591.42  6.175403e+06   1864553.0   
120 prog_dinamica     100.0   3637851.53  4.192951e+06    809389.0   
    rec_con_memo      100.0  11947287.01  7.492544e+06   2774833.0   
150 prog_dinamica     100.0   6280899.77  5.792716e+06   1220840.0   
    rec_con_memo      100.0  22976257.45  8.975174e+06   4583720.0   
200 prog_dinamica     100.0   8394005.30  5.891054e+06   2318280.0   
    rec_con_memo      100.0  28131455.02  1.038191e+07   9591498.0   
400 prog_dinamica     100.0  25067883.12  1.117707e+07   9294587.0   
    rec_con_memo      100.0  91303845.44  2.925778e+07  35085738.0   

                              25%         50%           75%          max  
n   algoritmo                                                             
4   fuerza_bruta_rec      6579.50      7361.0  9.437000e+03    5228593.0  
    prog_dinamica         5747.00      6749.0  7.851000e+03      54548.0  
    rec_con_memo          6347.75      7268.5  9.537750e+03      48364.0  
5   fuerza_bruta_rec     10066.25     10835.5  1.173925e+04    6051870.0  
    prog_dinamica         6265.75      7002.5  7.829000e+03      18523.0  
    rec_con_memo          7277.00      8140.5  9.291750e+03      28782.0  
7   fuerza_bruta_rec     30918.00     32805.5  3.436600e+04    3077909.0  
    prog_dinamica         9004.00      9525.0  1.015525e+04      47312.0  
    rec_con_memo         11261.50     11928.0  1.259325e+04      27957.0  
10  fuerza_bruta_rec    209965.50    235184.5  2.540158e+05   10855554.0  
    prog_dinamica        12984.00     13800.0  1.460550e+04      77830.0  
    rec_con_memo         17592.00     19033.0  1.982650e+04   10482421.0  
14  fuerza_bruta_rec   6633096.00   8484838.0  1.070574e+07   34759270.0  
    prog_dinamica        20798.25     22484.5  2.321525e+04    2045099.0  
    rec_con_memo         32705.25     35018.0  3.739375e+04    3133882.0  
15  prog_dinamica        21793.50     23061.0  2.462275e+04   10067714.0  
    rec_con_memo         34861.25     37358.5  3.943450e+04     134854.0  
18  prog_dinamica        28780.75     30442.5  3.247525e+04    2077288.0  
    rec_con_memo         48546.75     51272.5  5.461850e+04     338449.0  
20  prog_dinamica        35029.75     36391.0  3.846550e+04    5087460.0  
    rec_con_memo         60283.00     62661.5  6.709950e+04   17316128.0  
22  prog_dinamica        40799.75     42505.0  4.459000e+04   14950097.0  
    rec_con_memo         72464.75     76367.5  8.079050e+04   17125300.0  
24  prog_dinamica        47069.75     49286.5  5.793950e+04   10087121.0  
    rec_con_memo         84654.75     90671.0  9.742625e+04    7138938.0  
25  prog_dinamica        52049.50     53572.5  7.411500e+04    5612727.0  
    rec_con_memo         97815.75    106070.5  4.118098e+05   10255853.0  
30  prog_dinamica        69210.75     72558.5  7.971600e+04    6368526.0  
    rec_con_memo        134190.00    138289.5  1.476828e+05   14411558.0  
35  prog_dinamica        90748.75     92665.5  9.834300e+04   15138351.0  
    rec_con_memo        177450.25    184611.0  1.968300e+05   11004801.0  
40  prog_dinamica       115768.00    120788.5  1.313565e+05   10334988.0  
    rec_con_memo        229963.50    240018.5  2.565320e+05   12921403.0  
45  prog_dinamica       141692.50    149743.0  1.627680e+05   22139272.0  
    rec_con_memo        284878.75    300001.0  3.153990e+05   20453304.0  
50  prog_dinamica       175151.25    182002.5  2.112798e+05   13362334.0  
    rec_con_memo        353023.75    371148.0  4.635205e+05    8223964.0  
60  prog_dinamica       235094.25    248504.5  2.608910e+05    5383811.0  
    rec_con_memo        580844.75    610087.5  6.325818e+05   10583409.0  
70  prog_dinamica       319789.00    338987.0  3.547852e+05    7053841.0  
    rec_con_memo        920175.25    976770.5  2.668450e+06   11443745.0  
80  prog_dinamica       421055.75    438301.5  4.677680e+05   13468494.0  
    rec_con_memo       1320182.25   1372022.5  5.079953e+06   30016718.0  
90  prog_dinamica       514104.75    534458.5  5.643522e+05    8652543.0  
    rec_con_memo       1628564.25   1749333.0  4.737237e+06   31002407.0  
100 prog_dinamica       660878.25    702149.5  1.728142e+06   27192531.0  
    rec_con_memo       2114750.75   4892089.0  9.350509e+06   36134365.0  
120 prog_dinamica       973942.25   1151460.5  3.981179e+06   17165842.0  
    rec_con_memo       5220622.75  10139997.0  1.623446e+07   35221473.0  
150 prog_dinamica      1545223.25   3558646.5  1.057733e+07   23208241.0  
    rec_con_memo      15773881.75  23921804.5  2.941298e+07   42206423.0  
200 prog_dinamica      2836731.00   7477735.5  1.072993e+07   37967637.0  
    rec_con_memo      20456725.00  26636828.0  3.445102e+07   68158565.0  
400 prog_dinamica     17523201.75  23917694.5  3.151054e+07   59705813.0  
    rec_con_memo      71585465.00  91686394.5  1.118647e+08  151425091.0  
In [ ]:
# 1.1) Descripción más específica en TIEMPO

desc_tiempos_especificos = df_ok.groupby(['category_size','algoritmo', 'tipo_instancia'])['tiempo_ejecucion'].describe()
print(desc_tiempos_especificos)
                                               count          mean  \
category_size algoritmo        tipo_instancia                        
L             prog_dinamica    estructurada    250.0  7.566642e+05   
                               uniforme        250.0  7.062782e+05   
              rec_con_memo     estructurada    250.0  2.369861e+06   
                               uniforme        250.0  2.243606e+06   
M             prog_dinamica    estructurada    250.0  5.510921e+05   
                               uniforme        250.0  4.038209e+05   
              rec_con_memo     estructurada    250.0  1.191087e+06   
                               uniforme        250.0  7.647399e+05   
S             prog_dinamica    estructurada    250.0  2.986697e+05   
                               uniforme        250.0  1.721169e+05   
              rec_con_memo     estructurada    250.0  3.788323e+05   
                               uniforme        250.0  2.324267e+05   
XL            prog_dinamica    estructurada    250.0  8.509651e+06   
                               uniforme        250.0  9.704886e+06   
              rec_con_memo     estructurada    250.0  3.102510e+07   
                               uniforme        250.0  3.340387e+07   
XS            fuerza_bruta_rec estructurada    250.0  2.039827e+06   
                               uniforme        250.0  1.912125e+06   
              prog_dinamica    estructurada    250.0  2.063168e+04   
                               uniforme        250.0  1.284917e+04   
              rec_con_memo     estructurada    250.0  5.876844e+04   
                               uniforme        250.0  4.040513e+04   

                                                        std        min  \
category_size algoritmo        tipo_instancia                            
L             prog_dinamica    estructurada    1.578391e+06   151026.0   
                               uniforme        1.597977e+06   153035.0   
              rec_con_memo     estructurada    3.433891e+06   303578.0   
                               uniforme        3.612918e+06   314252.0   
M             prog_dinamica    estructurada    2.155632e+06    46350.0   
                               uniforme        1.587320e+06    48099.0   
              rec_con_memo     estructurada    2.873608e+06    69245.0   
                               uniforme        1.885758e+06    89934.0   
S             prog_dinamica    estructurada    1.430141e+06    20214.0   
                               uniforme        1.136373e+06    19106.0   
              rec_con_memo     estructurada    1.931710e+06    30638.0   
                               uniforme        1.368300e+06    31611.0   
XL            prog_dinamica    estructurada    9.465289e+06   577108.0   
                               uniforme        1.170241e+07   588561.0   
              rec_con_memo     estructurada    3.259128e+07  1963090.0   
                               uniforme        3.545423e+07  1864553.0   
XS            fuerza_bruta_rec estructurada    4.417220e+06     5507.0   
                               uniforme        3.995924e+06     5808.0   
              prog_dinamica    estructurada    1.287929e+05     4761.0   
                               uniforme        7.684271e+03     5348.0   
              rec_con_memo     estructurada    6.619935e+05     4969.0   
                               uniforme        2.606173e+05     6106.0   

                                                       25%         50%  \
category_size algoritmo        tipo_instancia                            
L             prog_dinamica    estructurada      250980.25    373424.5   
                               uniforme          240443.75    332175.0   
              rec_con_memo     estructurada      612876.25   1313042.0   
                               uniforme          600230.00    945865.5   
M             prog_dinamica    estructurada       72611.75     97090.5   
                               uniforme           73229.50     99440.5   
              rec_con_memo     estructurada      145410.25    219716.5   
                               uniforme          137216.75    206478.5   
S             prog_dinamica    estructurada       29386.00     37155.0   
                               uniforme           28853.75     37612.0   
              rec_con_memo     estructurada       50026.50     63934.5   
                               uniforme           49148.00     65934.0   
XL            prog_dinamica    estructurada     1026077.00   4669840.5   
                               uniforme         1416859.50   4053184.5   
              rec_con_memo     estructurada    10129861.25  20274569.5   
                               uniforme         8304624.75  21177878.5   
XS            fuerza_bruta_rec estructurada       10128.50     32545.5   
                               uniforme           10912.50     33329.0   
              prog_dinamica    estructurada        7053.50      9993.0   
                               uniforme            7218.00     10285.5   
              rec_con_memo     estructurada        8226.00     12444.5   
                               uniforme            8609.25     12692.0   

                                                       75%          max  
category_size algoritmo        tipo_instancia                            
L             prog_dinamica    estructurada      505546.00   13362334.0  
                               uniforme          471656.75   13468494.0  
              rec_con_memo     estructurada     2529583.75   31002407.0  
                               uniforme         1760865.25   30016718.0  
M             prog_dinamica    estructurada      139736.00   22139272.0  
                               uniforme          139580.00   15138351.0  
              rec_con_memo     estructurada      296358.50   20453304.0  
                               uniforme          297841.25   12921403.0  
S             prog_dinamica    estructurada       46679.50   13097994.0  
                               uniforme           45998.75   14950097.0  
              rec_con_memo     estructurada       85105.25   17316128.0  
                               uniforme           78443.00   12541518.0  
XL            prog_dinamica    estructurada    12350990.00   41645693.0  
                               uniforme        13628970.75   59705813.0  
              rec_con_memo     estructurada    33928007.00  151425091.0  
                               uniforme        37194515.00  142151406.0  
XS            fuerza_bruta_rec estructurada      254752.00   34759270.0  
                               uniforme          270888.00   31375422.0  
              prog_dinamica    estructurada       14984.00    2045099.0  
                               uniforme           15646.25      77830.0  
              rec_con_memo     estructurada       20085.50   10482421.0  
                               uniforme           20851.75    3133882.0  
In [ ]:
# 1.3) Descripción más específica en TIEMPO

desc_tiempos_especificos = df_ok.groupby(['category_size','tipo_instancia'])['tiempo_ejecucion'].describe()
print(desc_tiempos_especificos)
                              count          mean           std       min  \
category_size tipo_instancia                                                
L             estructurada    500.0  1.563263e+06  2.789096e+06  151026.0   
              uniforme        500.0  1.474942e+06  2.894779e+06  153035.0   
M             estructurada    500.0  8.710897e+05  2.557706e+06   46350.0   
              uniforme        500.0  5.842804e+05  1.750537e+06   48099.0   
S             estructurada    500.0  3.387510e+05  1.698300e+06   20214.0   
              uniforme        500.0  2.022718e+05  1.256796e+06   19106.0   
XL            estructurada    500.0  1.976738e+07  2.649015e+07  577108.0   
              uniforme        500.0  2.155438e+07  2.891833e+07  588561.0   
XS            estructurada    750.0  7.064090e+05  2.743759e+06    4761.0   
              uniforme        750.0  6.551264e+05  2.474280e+06    5348.0   

                                     25%         50%          75%          max  
category_size tipo_instancia                                                    
L             estructurada     346540.25    540665.5   1370822.25   31002407.0  
              uniforme         330495.25    520558.5   1034435.25   30016718.0  
M             estructurada      95063.75    141733.0    236791.00   22139272.0  
              uniforme          94506.25    137811.0    232094.75   15138351.0  
S             estructurada      35559.75     48531.0     72356.25   17316128.0  
              uniforme          36031.00     47232.0     68547.00   14950097.0  
XL            estructurada    2820224.25  11507369.0  23742456.50  151425091.0  
              uniforme        2770063.50  10814184.0  28355439.00  142151406.0  
XS            estructurada       8182.50     12444.5     31049.00   34759270.0  
              uniforme           8892.25     13239.5     31287.00   31375422.0  
In [ ]:
# 2) Descripción general en ESPACIO

desc_espacio = df_ok.groupby(['n','algoritmo'])['memoria_max_mb'].describe()
print(desc_espacio)
                      count      mean       std  min  25%  50%  75%       max
n   algoritmo                                                                
4   fuerza_bruta_rec  100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
5   fuerza_bruta_rec  100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
7   fuerza_bruta_rec  100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
10  fuerza_bruta_rec  100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
14  fuerza_bruta_rec  100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
15  prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
18  prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
20  prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
22  prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
24  prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
25  prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
30  prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
35  prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
40  prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
45  prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
50  prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
60  prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.003984  0.024686  0.0  0.0  0.0  0.0  0.199219
70  prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000937  0.008989  0.0  0.0  0.0  0.0  0.089844
80  prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
90  prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.002383  0.023828  0.0  0.0  0.0  0.0  0.238281
100 prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.001016  0.010156  0.0  0.0  0.0  0.0  0.101562
120 prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
150 prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
200 prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
400 prog_dinamica     100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
    rec_con_memo      100.0  0.000000  0.000000  0.0  0.0  0.0  0.0  0.000000
In [ ]:
# 2.1) Descripción más específica en ESPACIO

desc_tiempos_especificos = df_ok.groupby(['category_size', 'tipo_instancia'])['memoria_max_mb'].describe()
print(desc_tiempos_especificos)
                              count      mean       std  min  25%  50%  75%  \
category_size tipo_instancia                                                  
L             estructurada    500.0  0.000508  0.007759  0.0  0.0  0.0  0.0   
              uniforme        500.0  0.000953  0.013882  0.0  0.0  0.0  0.0   
M             estructurada    500.0  0.000000  0.000000  0.0  0.0  0.0  0.0   
              uniforme        500.0  0.000000  0.000000  0.0  0.0  0.0  0.0   
S             estructurada    500.0  0.000000  0.000000  0.0  0.0  0.0  0.0   
              uniforme        500.0  0.000000  0.000000  0.0  0.0  0.0  0.0   
XL            estructurada    500.0  0.000000  0.000000  0.0  0.0  0.0  0.0   
              uniforme        500.0  0.000203  0.004542  0.0  0.0  0.0  0.0   
XS            estructurada    750.0  0.000000  0.000000  0.0  0.0  0.0  0.0   
              uniforme        750.0  0.000000  0.000000  0.0  0.0  0.0  0.0   

                                   max  
category_size tipo_instancia            
L             estructurada    0.148438  
              uniforme        0.238281  
M             estructurada    0.000000  
              uniforme        0.000000  
S             estructurada    0.000000  
              uniforme        0.000000  
XL            estructurada    0.000000  
              uniforme        0.101562  
XS            estructurada    0.000000  
              uniforme        0.000000  
In [ ]:
def plot_tiempo_vs_n(df_ok: pd.DataFrame, title: str = "Tiempo de ejecución promedio vs. n (por algoritmo)\n", palette = 'cubehelix'):

    # --- Configuración General ---
    sns.set_theme(
        style="whitegrid",  # Fondo blanco con rejilla sutil
        palette= palette,  # Paleta de colores "viridis"
        font_scale=1.1,     # Escala de fuente ligeramente mayor
        rc={
            "figure.figsize": (6, 4),       # Tamaño de la figura
            "axes.titlesize": 16,           # Tamaño del título
            "axes.labelsize": 10,           # Tamaño de las etiquetas de los ejes
            "xtick.labelsize": 10,          # Tamaño de las etiquetas del eje x
            "ytick.labelsize": 10,          # Tamaño de las etiquetas del eje y
            "legend.fontsize": 10,          # Tamaño de la fuente de la leyenda
            "legend.title_fontsize": 10,   # Tamaño del título de la leyenda
            "axes.spines.top": False,     # Quitar borde superior
            "axes.spines.right": False,    # Quitar borde derecho
            "axes.edgecolor": "0.2",       # Color del borde de los ejes (gris oscuro)
            "grid.color": "0.8",          # Color de la rejilla (gris claro)
            "grid.linestyle": "--",       # Estilo de línea de la rejilla (discontinua)
            "lines.linewidth": 2.5,        # Grosor de las líneas
            "lines.markersize": 8,        # Tamaño de los marcadores
            "figure.dpi": 150            # Resolución en puntos por pulgada para la exportación
        }
    )

    # --- Creación del Gráfico ---
    plt.figure()  # Crear una nueva figura (aunque ya está en rc, es buena práctica)

    # Usar lineplot de Seaborn, con intervalos de confianza (desviación estándar)
    ax = sns.lineplot(
        data=df_ok,
        x='n',
        y='tiempo_ejecucion',
        hue='algoritmo',
        style='algoritmo',  # Usar diferentes estilos de línea además del color
        estimator='mean',  # Mostrar la media
        errorbar='ci',      # Mostrar la desviación estándar como intervalo de confianza "ci", "pi", "se", or "sd"
        markers=True,      # Mostrar marcadores en los puntos
        dashes=False,      # Evita que seaborn use líneas discontinuas, controlamos con 'style'
        alpha=0.8          # Ligera transparencia para las líneas
    )

    # --- Personalización del Gráfico ---
    ax.set_title(title, fontweight='bold', pad=20)  # Título en negrita, con espacio
    ax.set_xlabel("Tamaño de entrada (n)", labelpad=12) #Nombre y espacio eje X
    ax.set_ylabel("Tiempo de ejecución (ns)", labelpad=12) #Nombre y espacio eje Y

    # --- Formato del Eje Y (Científico si es necesario) ---
    # Si los tiempos son muy pequeños, usar notación científica
    if df_ok['tiempo_ejecucion'].max() < 0.01:
        ax.yaxis.set_major_formatter(ticker.ScalarFormatter(useMathText=True))
        ax.ticklabel_format(style='sci', axis='y', scilimits=(0, 0))
        ax.yaxis.offsetText.set_fontsize(10)  # Ajustar tamaño de la notación científica

    # --- Leyenda ---
    ax.legend(title="Algoritmo", loc="lower right", frameon=True, framealpha=0.9, ncol=1) #Título, ubicación, marco, etc.

    #--- Escala Logarítmica (Opcional) ---
    # Si quieres una escala logarítmica en el eje y (útil para ver diferencias exponenciales):
    ax.set_yscale('log')
    ax.set_ylabel("Tiempo de ejecución (ns) - Escala Logarítmica")  # Cambiar etiqueta

    # --- Ajustes Finales y Mostrar/Guardar ---
    plt.tight_layout()  # Ajustar automáticamente los márgenes
    plt.show()
    # Para guardar la figura en alta resolución:
    # plt.savefig("tiempo_vs_n.png", dpi=300, bbox_inches='tight') #Ajusta nombre y resolución
In [ ]:
# 2) Gráfico de líneas: tiempo vs n
plt.figure(figsize=(6,4))
sns.lineplot(data=df_ok, x='n', y='tiempo_ejecucion', hue='algoritmo',
             estimator='mean', markers=True, palette = 'inferno')
plt.title("Tiempo de ejecución promedio vs. n (por algoritmo)\n")
plt.ylabel("Tiempo de ejecución (ns)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
No description has been provided for this image
In [ ]:
df_uniforme = df_ok[df_ok['tipo_instancia'] == 'uniforme']
plt.figure(figsize=(6,4))
sns.lineplot(data=df_uniforme, x='n', y='tiempo_ejecucion', hue='algoritmo',
             estimator='mean', markers=True, palette = 'inferno')
plt.title("Tiempo de ejecución promedio con instancias \nUNIFORMES vs. n (por algoritmo)\n")
plt.ylabel("Tiempo de ejecución (ns)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
No description has been provided for this image
In [ ]:
df_estructurada = df_ok[df_ok['tipo_instancia'] == 'estructurada']
plt.figure(figsize=(6,4))
sns.lineplot(data=df_estructurada, x='n', y='tiempo_ejecucion', hue='algoritmo',
             estimator='mean', markers=True, palette = 'inferno')
plt.title("Tiempo de ejecución promedio con instancias\n ESTRUCTURADAS vs. n (por algoritmo)\n")
plt.ylabel("Tiempo de ejecución (ns)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
No description has been provided for this image
In [ ]:
# Filtra el DataFrame para incluir solo los algoritmos deseados
df_subset = df_ok[df_ok['algoritmo'].isin(['prog_dinamica', 'rec_con_memo'])]

plt.figure(figsize=(6,4))
sns.lineplot(data=df_subset, x='n', y='tiempo_ejecucion', hue='algoritmo',
             estimator='mean', markers=True, palette='inferno')
plt.title("Tiempo de ejecución promedio vs. n (por algoritmo)\n")
plt.ylabel("Tiempo de ejecución (ns)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
No description has been provided for this image
In [ ]:
df_ok_hasta_n14 = df_ok[df_ok['n'] <= 14]
In [ ]:
plt.figure(figsize=(6,4))
sns.lineplot(data=df_ok_hasta_n14, x='n', y='tiempo_ejecucion', hue='algoritmo',
             estimator='mean', markers=True, palette = 'inferno')
plt.title("Tiempo de ejecución promedio vs. n (por algoritmo)\n")
plt.ylabel("Tiempo de ejecución (ns)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
No description has been provided for this image
In [ ]:
plot_tiempo_vs_n(df_ok)
No description has been provided for this image
In [ ]:
plot_tiempo_vs_n(df_subset, palette="tab10") #tab10, hls, Spectral, husl
No description has been provided for this image

Uso de memoria:¶

In [ ]:
plt.figure(figsize=(6,4))
sns.lineplot(data=df_ok, x='n', y='memoria_max_mb', hue='algoritmo',
             estimator='mean', markers=True, palette = 'tab10')
plt.title("Uso de Memoria (MB) vs. n")
plt.ylabel("Memoria (MB)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
No description has been provided for this image
In [ ]:
plt.figure(figsize=(6,4))
sns.lineplot(data=df_subset, x='n', y='memoria_max_mb', hue='algoritmo',
             estimator='mean', markers=True, palette = 'tab10')
plt.title("Uso de Memoria (MB) vs. n")
plt.ylabel("Memoria (MB)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
No description has been provided for this image

Gráficos vs crecimientos teóricos¶

In [ ]:
# definir la función 2^n hasta 15

def f(n):
    return 2**n

x_bruta = np.arange(1, 15)
y_bruta = f(x_bruta)
In [ ]:
# definir los n^2

def f2(n):
    return n**2

x_n2 = np.arange(1, 400)
y_n2 = f2(x_n2)
In [ ]:
e1 = 8e+2
e2 = 6.5e+2
e3 = 17e+1
In [ ]:
plt.figure(figsize=(6,4))
sns.lineplot(data=df_ok, x='n', y='tiempo_ejecucion', hue='algoritmo',
             estimator='mean', markers=True, palette = 'inferno')
sns.lineplot(x=x_bruta, y=e1*y_bruta, color='green', linestyle=':', label='$2^{n}$ fuerza bruta')
sns.lineplot(x=x_n2, y=e2*y_n2, color='magenta', linestyle=':', label='$n^{2}$ Rec memo')
sns.lineplot(x=x_n2, y=e3*y_n2, color='orangered', linestyle=':', label='$n^{2}$ DP')
plt.title("Tiempo de ejecución promedio vs.\n Tiempos teóricos por algoritmo\n")
plt.ylabel("Tiempo de ejecución (ns)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
No description has been provided for this image

Más estadística descriptiva:¶

In [ ]:
def boxplot(data=df_ok, palette='viridis'):
  plt.figure(figsize=(10, 5))
  sns.boxplot(
      data=data,
      x='n',
      y='tiempo_ejecucion',
      hue='algoritmo',
      palette=palette,
      showfliers=False  # Opcional: ocultar outliers si hay muchos
  )
  plt.yscale('log')  # Escala logarítmica para mejor visualización
  plt.title("Distribución de Tiempos de Ejecución por Algoritmo y Tamaño n (Escala Logarítmica)\n")
  plt.xlabel("Tamaño (n)")
  plt.ylabel("Tiempo de Ejecución (ns)")
  plt.legend(bbox_to_anchor=(1.05, 1), loc='upper left')
  plt.show()
In [ ]:
boxplot(df_ok, 'bright')
No description has been provided for this image
In [ ]:
def grafico_barras_categorias(data=df_ok, palette='viridis'):
    """Barras agrupadas por categoría de tamaño"""
    plt.figure(figsize=(10, 6))
    sns.barplot(
        data=data,
        x='category_size',
        y='tiempo_ejecucion',
        hue='algoritmo',
        palette=palette,
        estimator='median',
        errorbar=None
    )
    plt.yscale('log')
    plt.title("Tiempo Promedio por Categoría de Tamaño")
    plt.xlabel("Categoría")
    plt.ylabel("Tiempo (ns) - Escala Log")
    plt.legend(title='Algoritmo')
    plt.show()
In [ ]:
grafico_barras_categorias(df_ok, 'magma')
No description has been provided for this image
In [ ]:
def grafico_facetgrid_tipos(data=df_ok, palette='tab10'):
    """FacetGrid comparando tipos de instancia"""
    g = sns.FacetGrid(
        data,
        col='tipo_instancia',
        hue='algoritmo',
        palette=palette,
        height=4,
        aspect=1.2
    )
    g.map(sns.lineplot, 'n', 'tiempo_ejecucion', estimator='mean', marker='o')
    g.add_legend()
    g.set_axis_labels("Tamaño (n)", "Tiempo (ns)")
    g.set_titles("Tipo de Instancia: {col_name}")
    plt.subplots_adjust(top=0.8)
    g.fig.suptitle("Comparación entre Tipos de Instancia")
    plt.show()
In [ ]:
grafico_facetgrid_tipos(df_ok, 'inferno')
No description has been provided for this image
In [ ]:
def grafico_interactivo_plotly(data=df_ok, palette='viridis'):
    """Gráfico interactivo con Plotly"""
    fig = px.line(
        data,
        x='n',
        y='tiempo_ejecucion',
        color='algoritmo',
        line_group='replica_id',
        facet_col='tipo_instancia',
        log_y=True,
        title="Análisis Interactivo de Tiempos",
        labels={'n': 'Tamaño (n)', 'tiempo_ejecucion': 'Tiempo (ns)'},
        color_discrete_sequence=sns.color_palette(palette).as_hex()
    )
    fig.update_layout(height=700, width=1000)
    fig.show()
In [ ]:
grafico_interactivo_plotly(df_ok, 'plasma')
In [ ]:
def scatter_tiempo_vs_memoria(df=None, palette="magma"):
    """
    Muestra un diagrama de dispersión (scatterplot) de tiempo_ejecucion vs memoria_max_mb,
    coloreado por algoritmo. Útil para ver correlación entre tiempo y memoria.
    """
    if df is None:
        print("Advertencia: df es None. Usando df_ok por defecto.")
        df = df_ok

    plt.figure(figsize=(6,4))
    sns.scatterplot(
        data=df,
        x='memoria_max_mb',
        y='tiempo_ejecucion',
        hue='algoritmo',
        palette=palette
    )
    plt.title("Relación entre Tiempo y Memoria por Algoritmo")
    plt.xlabel("Memoria (MB)")
    plt.ylabel("Tiempo de ejecución (ns)")
    plt.legend()
    plt.tight_layout()
    plt.show()
In [ ]:
scatter_tiempo_vs_memoria(df_ok, 'inferno')
No description has been provided for this image

5.2 Contraste de Hipótesis (ANOVA, Pruebas Post-hoc, t-Test, etc.)¶

5.2.1 ANOVA¶

Para la Hipótesis 1 (tiempo de ejecución):

Podemos realizar un ANOVA de un factor (algoritmo) para un n fijo, o un ANOVA de dos factores (algoritmo, n). Ejemplo con statsmodels:

In [ ]:
# Filtramos un n mediano, por ejemplo n=14 (donde todos tienen datos)

df_n14 = df_ok[df_ok['n'] == 14]
model = ols('tiempo_ejecucion ~ C(algoritmo)', data=df_n14).fit()
anova_results = sm.stats.anova_lm(model, typ=2)
print(anova_results)
                    sum_sq     df           F        PR(>F)
C(algoritmo)  5.387558e+15    2.0  369.190914  2.896695e-81
Residual      2.167042e+15  297.0         NaN           NaN
  • Significado del p-valor (ANOVA)

Como el valor $PR(>F) = 2.896695 × 10^{-81}$ es extremadamente pequeño (mucho menor a $0.05$ o incluso $0.001$).

Esto indica que podemos rechazar la hipótesis nula $H_0$ de que "todas las medias de las mediciones (una por cada algoritmo) son iguales" en el tamaño $n=14$.

En otras palabras, al menos un algoritmo difiere significativamente de los demás en la métrica que has analizado (puede que sea el tiempo de ejecución, la versión logarítmica de tiempo, etc.).

In [ ]:
model = ols('tiempo_ejecucion ~ C(algoritmo)', data=df_ok_hasta_n14).fit()
anova_results = sm.stats.anova_lm(model, typ=2)
print(anova_results)
                    sum_sq      df           F        PR(>F)
C(algoritmo)  1.258443e+15     2.0  105.050401  2.030166e-43
Residual      8.966597e+15  1497.0         NaN           NaN
  • Significado del p-valor (ANOVA)

Como el valor $PR(>F) = 2.030166 × 10^{-43}$ es extremadamente pequeño (mucho menor a $0.05$ o incluso $0.001$).

Esto indica que podemos rechazar la hipótesis nula $H_0$ de que "todas las medias de las mediciones (una por cada algoritmo) son iguales" en el tamaño $n\leq 14$.

En otras palabras, al menos un algoritmo difiere significativamente de los demás en la métrica que has analizado (puede que sea el tiempo de ejecución, la versión logarítmica de tiempo, etc.).

In [ ]:
# Usamos todos los tamaños n de las instancias

model = ols('tiempo_ejecucion ~ C(algoritmo)', data=df_ok).fit()
anova_results = sm.stats.anova_lm(model, typ=2)
print(anova_results)
                    sum_sq      df          F        PR(>F)
C(algoritmo)  3.520056e+16     2.0  89.383672  6.295298e-39
Residual      1.082398e+18  5497.0        NaN           NaN
  • Significado del p-valor (ANOVA)

Como el valor $PR(>F) = 6.295298 × 10^{-39}$ es extremadamente más pequeño (mucho menor a $0.05$ o incluso $0.001$).

Esto indica que podemos rechazar la hipótesis nula $H_0$ de que "todas las medias de las mediciones (una por cada algoritmo) son iguales". Sin embargo hay un sesgo en el tamaño de instancias de: fuerza_bruta_rec, entonces solo podemos comparar directamente rec_con_memo con prog_dinamica y si queremos compararlos a su vez con fuerza_bruta_rec, debe ser en el intervalo $n = [1,15].$

En otras palabras, al menos un algoritmo difiere significativamente de los demás en la métrica que has analizado (puede que sea el tiempo de ejecución, la versión logarítmica de tiempo, etc.).

In [ ]:
# Usamos todos los tamaños n de las instancias

model = ols('tiempo_ejecucion ~ C(algoritmo)*C(n)', data=df_ok).fit()
anova_results = sm.stats.anova_lm(model, typ=2)
print(anova_results)
                         sum_sq      df          F    PR(>F)
C(algoritmo)       7.405152e+14     2.0  13.345624  0.000002
C(n)               1.150145e+15    24.0   1.727333  0.015118
C(algoritmo):C(n)  9.068080e+09    48.0   0.000007  0.997918
Residual           1.510647e+17  5445.0        NaN       NaN
/usr/local/lib/python3.11/dist-packages/statsmodels/base/model.py:1894: ValueWarning:

covariance of constraints does not have full rank. The number of constraints is 48, but rank is 1

Aquí de hecho python nos hace la recomendación de que esto no se debería hacer: ValueWarning: covariance of constraints does not have full rank. The number of constraints is 48, but rank is 1 warnings.warn('covariance of constraints does not have full ' Dado que al agregar $*C(n)$ en el model ols estamos viendo sí hay diferencias entre las instancias y los algoritmos y aunque es cierto hay una infraproporción de uno de los algorimtos, en este caso: fuerza_bruta_rec. Ya ahondaremos más en las pruebas Tukey y veremos el sesgo a profundidad...

  • Conclusión General del ANOVA

Existe un efecto significativo del factor "algoritmo" sobre la variable dependiente (la que estés midiendo). No se sabe todavía cuáles algoritmos difieren entre sí; para eso se hace el análisis post-hoc (Tukey u otro).

5.2.2 Pruebas post-hoc¶

Luego, hacemos pruebas post-hoc (p.ej., TukeyHSD):

In [ ]:
# Prubea de los tres algoritmos en n = 14

mc1 = pairwise_tukeyhsd(df_n14['tiempo_ejecucion'], df_n14['algoritmo'], alpha=0.05)
print(mc1)
                Multiple Comparison of Means - Tukey HSD, FWER=0.05                 
====================================================================================
     group1          group2      meandiff  p-adj      lower         upper     reject
------------------------------------------------------------------------------------
fuerza_bruta_rec prog_dinamica -9014641.54    0.0 -9914466.7545 -8114816.3255   True
fuerza_bruta_rec  rec_con_memo -8964399.26    0.0 -9864224.4745 -8064574.0455   True
   prog_dinamica  rec_con_memo    50242.28 0.9905  -849582.9345   950067.4945  False
------------------------------------------------------------------------------------

Esto nos indica qué pares de algoritmos difieren significativamente con $n = 14$ y es obtiene:

  • fuerza_bruta_rec con rec_con_memo: $P$-valor $\approx 0$ y se rechaza (reject = True).
  • fuerza_bruta_rec con prog_dinamica: $P$-valor $\approx 0$ y se rechaza (reject = True).
  • rec_con_memo con prog_dinamica $P$-valor $= 0.9905$ y NO se rechaza (reject = False). Es decir con n = 14 no hay suficiente evidencia estadística, para decir que los dos algoritmos difieren en tiempo.
In [ ]:
# Prubea de los tres algoritmos en n < 15

mc2 = pairwise_tukeyhsd(df_ok_hasta_n14['tiempo_ejecucion'], df_ok_hasta_n14['algoritmo'], alpha=0.05)
print(mc2)
                 Multiple Comparison of Means - Tukey HSD, FWER=0.05                 
=====================================================================================
     group1          group2      meandiff   p-adj      lower         upper     reject
-------------------------------------------------------------------------------------
fuerza_bruta_rec prog_dinamica -1959235.566    0.0 -2322370.5323 -1596100.5997   True
fuerza_bruta_rec  rec_con_memo -1926389.202    0.0 -2289524.1683 -1563254.2357   True
   prog_dinamica  rec_con_memo    32846.364 0.9755  -330288.6023   395981.3303  False
-------------------------------------------------------------------------------------

Aquí observamos un resultado similar a la varianza tomada en $n = 14$ y ahora con $n \leq 14$ se obtiene:

  • fuerza_bruta_rec con rec_con_memo: $P$-valor $\approx 0$ y se rechaza (reject = True).
  • fuerza_bruta_rec con prog_dinamica: $P$-valor $\approx 0$ y se rechaza (reject = True).
  • rec_con_memo con prog_dinamica $P$-valor $= 0.9755$ y NO se rechaza (reject = False). Es decir con $n \leq 14$ no hay suficiente evidencia estadística, para decir que los dos algoritmos difieren en tiempo.
In [ ]:
# Ahora veamos rec_con_memo con prog_dinamica en todos los n, es decir entre 1 y 400

df_xl = df_subset[df_subset['algoritmo'].isin(['rec_con_memo', 'prog_dinamica'])]

mc3 = pairwise_tukeyhsd(df_xl['tiempo_ejecucion'], df_xl['algoritmo'], alpha=0.05)
print(mc3)
             Multiple Comparison of Means - Tukey HSD, FWER=0.05              
==============================================================================
    group1       group2      meandiff   p-adj    lower        upper     reject
------------------------------------------------------------------------------
prog_dinamica rec_con_memo 5057204.1656   0.0 4244535.1716 5869873.1596   True
------------------------------------------------------------------------------

Aquí observamos que rec_con_memo con prog_dinamica $P$-valor $\approx 0$ y se rechaza (reject = True).

Es decir con todos los $n$ hay suficiente evidencia estadística, para decir que los $2$ algoritmos difieren en tiempo.

In [ ]:
# Ahora hagamos la prueba con TODOS los n en los 3 algoritmos, para ver el sesgo entre
# Fuerza bruta y prgramación dinámica:

mc4 = pairwise_tukeyhsd(df_ok['tiempo_ejecucion'], df_ok['algoritmo'], alpha=0.05)
print(mc4)
                Multiple Comparison of Means - Tukey HSD, FWER=0.05                 
====================================================================================
     group1          group2      meandiff   p-adj      lower        upper     reject
------------------------------------------------------------------------------------
fuerza_bruta_rec prog_dinamica  137689.9644 0.9781 -1473906.5603 1749286.4891  False
fuerza_bruta_rec  rec_con_memo   5194894.13    0.0  3583297.6053 6806490.6547   True
   prog_dinamica  rec_con_memo 5057204.1656    0.0  4126748.4783 5987659.8529   True
------------------------------------------------------------------------------------

Esto nos indica qué pares de algoritmos difieren significativamente con todos los $n$ y se obtiene:

  • fuerza_bruta_rec con prog_dinamica: $P$-valor $= 0.9781 $ y NO se rechaza (reject = False). Sin embargo esto sucede porque NO se deberían comparar los experimentos de los dos algorimtos debido a la diferencia abismal de las varianzas entre las medidas de los tiempos, ya que los $n$ en que se evalúan son demasiado dispajeros hay 2000 experimentos menos en fuerza_bruta_rec. Por lo tanto ese p-valor está sesgado estadísticamente hablando.
  • fuerza_bruta_rec con rec_con_memo: $P$-valor $\approx 0$ y se rechaza (reject = True).
  • rec_con_memo con prog_dinamica $P$-valor $\approx 0$ y se rechaza (reject = True).

Es decir con todos los $n$ hay suficiente evidencia estadística, para decir que TODOS los algoritmos difieren en tiempo.

5.2.3 Prueba t-Test¶

Para comparar “Recursivo con Memo” vs. “Prog Dinámica” en términos de memoria, por ejemplo, podríamos filtrar esos dos algoritmos y realizar un t-test:

In [ ]:
df_rmemo = df_ok[df_ok['algoritmo'] == 'rec_con_memo']
df_pdin = df_ok[df_ok['algoritmo'] == 'prog_dinamica']

stat, pval = ttest_ind(df_rmemo['memoria_max_mb'], df_pdin['memoria_max_mb'], equal_var=False)
print(f"T-test Memoria Rec Memo vs Prog Din:\n\n ● statistic = {stat}\n ● P-value = {pval}")
T-test Memoria Rec Memo vs Prog Din:

 ● statistic = 2.248913319566825
 ● P-value = 0.02460477898059686

Si $p<0.05$, rechazamos la hipótesis nula de igualdad de medias en la meoria máxima almacenada en cada algoritmo (Recursivo memo y programación dinámica)

  • Interpretación del p-value

    El $p$-valor $= 0.0246047$ es mucho menor que cualquier umbral típico de significancia (por ejemplo, $α = 0.05$).

    Esto implica que se rechaza la hipótesis nula de igualdad de medias.

    En otras palabras, hay evidencia estadística suficiente para afirmar que Recursivo con Memo y Programación Dinámica difieren en promedio en su uso de memoria (al menos bajo los datos, supuestos y tamaño de muestra con que se corrió la prueba).

  • Conclusión

    Dado un $p$-value = $= 0.0246047$ (< $0.05$),se puede concluir que existe una diferencia significativa entre el uso de memoria de "Rec. con Memo" y "Prog. Dinámica". Dicho en palabras castizas:

    "Se detectan diferencias estadísticamente significativas entre la memoria consumida por el algoritmo recursivo con memoización y la programación dinámica, con el nivel de significancia del $5\%$"

5.3 Estadística Descriptiva usando tracemalloc¶

In [ ]:
# El archivo "resultados_optimizados.csv" es el más grande usado convertido
# del json de 80 MB con 50 réplicas en todos los tamaño y cargamos el usó:
# tracemalloc, para medir memoria, sin embargo veamos las diferencias:

df2 = pd.read_csv("resultados_optimizados2.csv")

df2.head() # primeras 5 filas del dataset
Out[ ]:
language category_size n tipo_instancia algoritmo replica_id tiempo_ejecucion memoria_max_mb costo_minimo status
0 Python XS 4 uniforme fuerza_bruta_rec 0 693276.0 0.000214 8.0 ok
1 Python XS 4 uniforme rec_con_memo 0 392730.0 0.000359 8.0 ok
2 Python XS 4 uniforme prog_dinamica 0 234636.0 0.000206 8.0 ok
3 Python XS 4 uniforme fuerza_bruta_rec 1 284901.0 0.000214 5.0 ok
4 Python XS 4 uniforme rec_con_memo 1 266267.0 0.000359 5.0 ok
In [ ]:
df2['status'].value_counts() # cuántos experimentos no pasaron por ser fuerza_bruta_recursiva
Out[ ]:
count
status
ok 5500
skipped_due_to_large_n 2000

In [ ]:
df2['memoria_max_mb'].value_counts() # contar los valores almacenados en la memoria
Out[ ]:
count
memoria_max_mb
0.000359 207
0.000214 200
0.000252 130
0.000519 102
0.001320 101
... ...
0.001747 1
0.001213 1
0.002815 1
0.002014 1
0.000946 1

69 rows × 1 columns


In [ ]:
df2.info() # Información de los valores nulos
<class 'pandas.core.frame.DataFrame'>
RangeIndex: 7500 entries, 0 to 7499
Data columns (total 10 columns):
 #   Column            Non-Null Count  Dtype  
---  ------            --------------  -----  
 0   language          7500 non-null   object 
 1   category_size     7500 non-null   object 
 2   n                 7500 non-null   int64  
 3   tipo_instancia    7500 non-null   object 
 4   algoritmo         7500 non-null   object 
 5   replica_id        7500 non-null   int64  
 6   tiempo_ejecucion  5500 non-null   float64
 7   memoria_max_mb    5500 non-null   float64
 8   costo_minimo      5500 non-null   float64
 9   status            7500 non-null   object 
dtypes: float64(3), int64(2), object(5)
memory usage: 586.1+ KB
In [ ]:
# Filtrar filas skip para quedarse solo con los valores no null

df2_ok = df2[df2['status'] == 'ok']

df2_ok.head()
Out[ ]:
language category_size n tipo_instancia algoritmo replica_id tiempo_ejecucion memoria_max_mb costo_minimo status
0 Python XS 4 uniforme fuerza_bruta_rec 0 693276.0 0.000214 8.0 ok
1 Python XS 4 uniforme rec_con_memo 0 392730.0 0.000359 8.0 ok
2 Python XS 4 uniforme prog_dinamica 0 234636.0 0.000206 8.0 ok
3 Python XS 4 uniforme fuerza_bruta_rec 1 284901.0 0.000214 5.0 ok
4 Python XS 4 uniforme rec_con_memo 1 266267.0 0.000359 5.0 ok
In [ ]:
df2_ok.info() # Corroborar valores no null
<class 'pandas.core.frame.DataFrame'>
Index: 5500 entries, 0 to 7499
Data columns (total 10 columns):
 #   Column            Non-Null Count  Dtype  
---  ------            --------------  -----  
 0   language          5500 non-null   object 
 1   category_size     5500 non-null   object 
 2   n                 5500 non-null   int64  
 3   tipo_instancia    5500 non-null   object 
 4   algoritmo         5500 non-null   object 
 5   replica_id        5500 non-null   int64  
 6   tiempo_ejecucion  5500 non-null   float64
 7   memoria_max_mb    5500 non-null   float64
 8   costo_minimo      5500 non-null   float64
 9   status            5500 non-null   object 
dtypes: float64(3), int64(2), object(5)
memory usage: 472.7+ KB
In [ ]:
# 1) Descripción general en TIEMPO

desc_tiempos2 = df2_ok.groupby(['n','algoritmo'])['tiempo_ejecucion'].describe()
print(desc_tiempos2)
                      count          mean           std          min  \
n   algoritmo                                                          
4   fuerza_bruta_rec  100.0  3.672911e+04  2.120665e+04      19579.0   
    prog_dinamica     100.0  3.717457e+04  1.113716e+04      23245.0   
    rec_con_memo      100.0  4.082959e+04  1.143614e+04      20744.0   
5   fuerza_bruta_rec  100.0  8.236321e+04  3.103806e+05      35216.0   
    prog_dinamica     100.0  5.254474e+04  1.271935e+05      25378.0   
    rec_con_memo      100.0  1.298036e+05  6.702027e+05      30012.0   
7   fuerza_bruta_rec  100.0  1.506144e+05  2.054311e+04     116730.0   
    prog_dinamica     100.0  4.509742e+04  1.636492e+04      31451.0   
    rec_con_memo      100.0  5.856351e+04  7.940189e+03      39281.0   
10  fuerza_bruta_rec  100.0  1.148520e+06  3.594599e+05     926737.0   
    prog_dinamica     100.0  5.843086e+04  7.575043e+03      47492.0   
    rec_con_memo      100.0  8.211965e+04  1.308444e+04      60290.0   
14  fuerza_bruta_rec  100.0  1.769650e+07  2.158101e+06   16427861.0   
    prog_dinamica     100.0  8.438599e+04  6.619772e+03      69105.0   
    rec_con_memo      100.0  1.332124e+05  1.924807e+04     105308.0   
15  prog_dinamica     100.0  9.024565e+04  1.766534e+04      78404.0   
    rec_con_memo      100.0  1.189243e+05  1.083920e+04      93793.0   
18  prog_dinamica     100.0  1.092477e+05  1.724999e+04      95914.0   
    rec_con_memo      100.0  1.470155e+05  1.243464e+04     128960.0   
20  prog_dinamica     100.0  1.224147e+05  1.136741e+04      89483.0   
    rec_con_memo      100.0  1.708389e+05  3.115107e+04     146110.0   
22  prog_dinamica     100.0  1.355932e+05  8.540056e+03     121348.0   
    rec_con_memo      100.0  1.874461e+05  1.743643e+04     149147.0   
24  prog_dinamica     100.0  1.526684e+05  1.146654e+04     140693.0   
    rec_con_memo      100.0  2.111226e+05  2.304676e+04     180997.0   
25  prog_dinamica     100.0  1.586851e+05  1.606765e+04     125010.0   
    rec_con_memo      100.0  2.056264e+05  3.266656e+04     169094.0   
30  prog_dinamica     100.0  1.976547e+05  1.666765e+04     160700.0   
    rec_con_memo      100.0  3.760805e+05  6.533605e+05     231628.0   
35  prog_dinamica     100.0  2.417241e+05  2.151446e+04     217485.0   
    rec_con_memo      100.0  3.583913e+05  2.939228e+04     317347.0   
40  prog_dinamica     100.0  2.826876e+05  1.596455e+04     249952.0   
    rec_con_memo      100.0  4.057497e+05  2.721344e+04     355352.0   
45  prog_dinamica     100.0  3.395203e+05  2.572842e+04     294460.0   
    rec_con_memo      100.0  5.485518e+05  1.799504e+05     471947.0   
50  prog_dinamica     100.0  3.936965e+05  5.001033e+04     339985.0   
    rec_con_memo      100.0  6.169000e+05  2.411156e+05     503667.0   
60  prog_dinamica     100.0  5.241085e+05  1.772389e+05     458012.0   
    rec_con_memo      100.0  9.590492e+05  3.949873e+05     809225.0   
70  prog_dinamica     100.0  6.715364e+05  2.626546e+05     549537.0   
    rec_con_memo      100.0  1.383319e+06  7.219193e+05    1138921.0   
80  prog_dinamica     100.0  8.526398e+05  4.269023e+05     711649.0   
    rec_con_memo      100.0  1.969988e+06  9.034087e+05    1558344.0   
90  prog_dinamica     100.0  1.242631e+06  1.350484e+06     859622.0   
    rec_con_memo      100.0  2.571467e+06  1.430751e+06    2033515.0   
100 prog_dinamica     100.0  1.082347e+06  3.891962e+04     965947.0   
    rec_con_memo      100.0  2.641339e+06  3.817436e+05    2336097.0   
120 prog_dinamica     100.0  1.460519e+06  1.202568e+05    1355543.0   
    rec_con_memo      100.0  3.614606e+06  1.504725e+05    3329525.0   
150 prog_dinamica     100.0  2.950594e+06  2.424416e+06    1924454.0   
    rec_con_memo      100.0  8.187272e+06  3.744949e+06    5250770.0   
200 prog_dinamica     100.0  6.106679e+06  3.783294e+06    3095022.0   
    rec_con_memo      100.0  1.644409e+07  7.180749e+06    9654442.0   
400 prog_dinamica     100.0  1.730509e+08  8.943885e+07   61511408.0   
    rec_con_memo      100.0  3.747097e+08  1.729599e+08  147055481.0   

                               25%          50%           75%          max  
n   algoritmo                                                               
4   fuerza_bruta_rec  2.947025e+04      30517.0  3.704225e+04     175175.0  
    prog_dinamica     3.345625e+04      34576.5  3.685425e+04     111264.0  
    rec_con_memo      3.196225e+04      40285.0  4.475675e+04      86960.0  
5   fuerza_bruta_rec  4.553400e+04      47609.5  5.459550e+04    3153310.0  
    prog_dinamica     3.117400e+04      37521.0  4.118325e+04    1300453.0  
    rec_con_memo      4.047000e+04      45018.0  4.853250e+04    6607098.0  
7   fuerza_bruta_rec  1.410185e+05     146981.0  1.565612e+05     293866.0  
    prog_dinamica     3.951500e+04      40798.0  4.785425e+04     185158.0  
    rec_con_memo      5.429625e+04      57298.0  6.216500e+04      84040.0  
10  fuerza_bruta_rec  1.064648e+06    1075833.0  1.099702e+06    3645519.0  
    prog_dinamica     5.598725e+04      56981.5  5.790550e+04     112700.0  
    rec_con_memo      7.710100e+04      79317.5  8.661300e+04     174028.0  
14  fuerza_bruta_rec  1.701074e+07   17135093.5  1.745112e+07   32736443.0  
    prog_dinamica     8.102375e+04      82094.5  8.552700e+04     129975.0  
    rec_con_memo      1.209040e+05     129130.5  1.410998e+05     211069.0  
15  prog_dinamica     8.477850e+04      85600.0  8.881375e+04     233386.0  
    rec_con_memo      1.125822e+05     117756.0  1.244415e+05     149348.0  
18  prog_dinamica     1.037500e+05     104737.0  1.106018e+05     257207.0  
    rec_con_memo      1.401650e+05     143668.5  1.528768e+05     230719.0  
20  prog_dinamica     1.170760e+05     118451.5  1.253740e+05     166568.0  
    rec_con_memo      1.584570e+05     164757.0  1.728425e+05     391035.0  
22  prog_dinamica     1.310965e+05     132343.5  1.396422e+05     173430.0  
    rec_con_memo      1.791205e+05     185819.5  1.924405e+05     298748.0  
24  prog_dinamica     1.458162e+05     147103.5  1.577512e+05     209415.0  
    rec_con_memo      1.988742e+05     207513.5  2.145770e+05     345448.0  
25  prog_dinamica     1.505238e+05     155387.5  1.644402e+05     263514.0  
    rec_con_memo      1.922615e+05     200279.5  2.091140e+05     474843.0  
30  prog_dinamica     1.898485e+05     192994.0  2.014632e+05     310673.0  
    rec_con_memo      2.549755e+05     282372.5  2.988870e+05    5427028.0  
35  prog_dinamica     2.315275e+05     236745.5  2.455768e+05     350723.0  
    rec_con_memo      3.363832e+05     356051.5  3.734735e+05     465412.0  
40  prog_dinamica     2.734710e+05     281214.0  2.882422e+05     354901.0  
    rec_con_memo      3.949392e+05     401703.5  4.094685e+05     594842.0  
45  prog_dinamica     3.273925e+05     336116.5  3.434048e+05     484192.0  
    rec_con_memo      5.153975e+05     524939.5  5.424295e+05    2304175.0  
50  prog_dinamica     3.798090e+05     384523.5  3.914088e+05     814279.0  
    rec_con_memo      5.701598e+05     580425.0  6.169790e+05    2964041.0  
60  prog_dinamica     4.904230e+05     502099.0  5.139478e+05    2255478.0  
    rec_con_memo      8.792430e+05     900108.5  9.349572e+05    4663551.0  
70  prog_dinamica     6.123922e+05     625462.0  6.432558e+05    2506247.0  
    rec_con_memo      1.243208e+06    1265614.0  1.307121e+06    6405015.0  
80  prog_dinamica     7.517260e+05     763020.5  7.821658e+05    3876504.0  
    rec_con_memo      1.655569e+06    1686565.0  1.757729e+06    6827680.0  
90  prog_dinamica     9.075702e+05     916527.5  9.350425e+05    7979248.0  
    rec_con_memo      2.117959e+06    2146267.5  2.222834e+06    9427040.0  
100 prog_dinamica     1.058985e+06    1081864.5  1.097238e+06    1212146.0  
    rec_con_memo      2.521265e+06    2562489.5  2.630959e+06    5541984.0  
120 prog_dinamica     1.410779e+06    1436889.0  1.465231e+06    2446152.0  
    rec_con_memo      3.535964e+06    3587753.5  3.641353e+06    4461993.0  
150 prog_dinamica     2.092257e+06    2129970.0  2.313710e+06   19191259.0  
    rec_con_memo      5.648558e+06    5777588.5  1.059332e+07   20320123.0  
200 prog_dinamica     3.452079e+06    3608632.5  8.487574e+06   18674089.0  
    rec_con_memo      1.033469e+07   13149656.0  2.163816e+07   34478442.0  
400 prog_dinamica     1.091877e+08  128164992.0  2.244060e+08  464731393.0  
    rec_con_memo      2.468323e+08  276588776.0  4.618460e+08  954458005.0  
In [ ]:
# 1.1) Descripción más específica en TIEMPO

desc_tiempos_especificos2 = df2_ok.groupby(['category_size','algoritmo', 'tipo_instancia'])['tiempo_ejecucion'].describe()
print(desc_tiempos_especificos2)
                                               count          mean  \
category_size algoritmo        tipo_instancia                        
L             prog_dinamica    estructurada    250.0  7.697207e+05   
                               uniforme        250.0  7.041240e+05   
              rec_con_memo     estructurada    250.0  1.521234e+06   
                               uniforme        250.0  1.479055e+06   
M             prog_dinamica    estructurada    250.0  2.444284e+05   
                               uniforme        250.0  2.436803e+05   
              rec_con_memo     estructurada    250.0  3.968647e+05   
                               uniforme        250.0  3.608951e+05   
S             prog_dinamica    estructurada    250.0  1.221438e+05   
                               uniforme        250.0  1.219240e+05   
              rec_con_memo     estructurada    250.0  1.656003e+05   
                               uniforme        250.0  1.685387e+05   
XL            prog_dinamica    estructurada    250.0  3.309286e+07   
                               uniforme        250.0  4.076757e+07   
              rec_con_memo     estructurada    250.0  7.334237e+07   
                               uniforme        250.0  8.889641e+07   
XS            fuerza_bruta_rec estructurada    250.0  3.797827e+06   
                               uniforme        250.0  3.848063e+06   
              prog_dinamica    estructurada    250.0  5.242056e+04   
                               uniforme        250.0  5.863287e+04   
              rec_con_memo     estructurada    250.0  7.634734e+04   
                               uniforme        250.0  1.014641e+05   

                                                        std        min  \
category_size algoritmo        tipo_instancia                            
L             prog_dinamica    estructurada    8.720940e+05   339985.0   
                               uniforme        5.010922e+05   344402.0   
              rec_con_memo     estructurada    1.161664e+06   503667.0   
                               uniforme        1.032636e+06   549940.0   
M             prog_dinamica    estructurada    6.551429e+04   126811.0   
                               uniforme        6.724938e+04   125010.0   
              rec_con_memo     estructurada    4.221863e+05   177615.0   
                               uniforme        1.698466e+05   169094.0   
S             prog_dinamica    estructurada    2.637412e+04    78404.0   
                               uniforme        2.452918e+04    82527.0   
              rec_con_memo     estructurada    3.729910e+04    93793.0   
                               uniforme        3.840276e+04   104810.0   
XL            prog_dinamica    estructurada    7.148272e+07   976357.0   
                               uniforme        8.577326e+07   965947.0   
              rec_con_memo     estructurada    1.499620e+08  2336097.0   
                               uniforme        1.806338e+08  2428502.0   
XS            fuerza_bruta_rec estructurada    6.930286e+06    21101.0   
                               uniforme        7.132745e+06    19579.0   
              prog_dinamica    estructurada    2.181978e+04    24002.0   
                               uniforme        8.156735e+04    23245.0   
              rec_con_memo     estructurada    9.418435e+04    23068.0   
                               uniforme        4.152926e+05    20744.0   

                                                      25%         50%  \
category_size algoritmo        tipo_instancia                           
L             prog_dinamica    estructurada     494392.25    628031.5   
                               uniforme         490736.00    626106.0   
              rec_con_memo     estructurada     876876.00   1256247.5   
                               uniforme         884062.75   1292126.0   
M             prog_dinamica    estructurada     191845.25    239479.0   
                               uniforme         188317.00    236251.0   
              rec_con_memo     estructurada     289963.75    354826.5   
                               uniforme         250009.50    362271.0   
S             prog_dinamica    estructurada     103664.75    119198.0   
                               uniforme         103921.75    118401.5   
              rec_con_memo     estructurada     140471.75    165223.5   
                               uniforme         141364.25    165373.5   
XL            prog_dinamica    estructurada    1406451.75   2219875.5   
                               uniforme        1418807.50   2106961.5   
              rec_con_memo     estructurada    3556553.75  10285327.0   
                               uniforme        3530098.50   5676643.0   
XS            fuerza_bruta_rec estructurada      46287.25    144410.5   
                               uniforme          46738.25    149974.0   
              prog_dinamica    estructurada      35050.75     45795.0   
                               uniforme          38866.75     49265.0   
              rec_con_memo     estructurada      43842.75     58214.5   
                               uniforme          45606.50     60804.5   

                                                       75%          max  
category_size algoritmo        tipo_instancia                            
L             prog_dinamica    estructurada      807284.50    7979248.0  
                               uniforme          771291.75    5315034.0  
              rec_con_memo     estructurada     1873447.25    9427040.0  
                               uniforme         1746115.50    9162728.0  
M             prog_dinamica    estructurada      289375.75     463012.0  
                               uniforme          290547.25     484192.0  
              rec_con_memo     estructurada      413059.00    5427028.0  
                               uniforme          415708.00    2304175.0  
S             prog_dinamica    estructurada      140985.50     257207.0  
                               uniforme          143016.50     233386.0  
              rec_con_memo     estructurada      192487.75     345448.0  
                               uniforme          192043.50     391035.0  
XL            prog_dinamica    estructurada    11426357.75  451821256.0  
                               uniforme         3875220.75  464731393.0  
              rec_con_memo     estructurada    26846731.00  954458005.0  
                               uniforme        12270567.25  947471571.0  
XS            fuerza_bruta_rec estructurada     1104656.75   21254607.0  
                               uniforme         1086490.00   32736443.0  
              prog_dinamica    estructurada       59365.25     173552.0  
                               uniforme           64778.50    1300453.0  
              rec_con_memo     estructurada       87079.25    1453383.0  
                               uniforme           88348.00    6607098.0  
In [ ]:
# 1.3) Descripción más específica en TIEMPO

desc_tiempos_especificos3 = df2_ok.groupby(['category_size','tipo_instancia'])['tiempo_ejecucion'].describe()
print(desc_tiempos_especificos3)
                              count          mean           std       min  \
category_size tipo_instancia                                                
L             estructurada    500.0  1.145477e+06  1.092871e+06  339985.0   
              uniforme        500.0  1.091589e+06  8.987910e+05  344402.0   
M             estructurada    500.0  3.206466e+05  3.112951e+05  126811.0   
              uniforme        500.0  3.022877e+05  1.417514e+05  125010.0   
S             estructurada    500.0  1.438721e+05  3.891505e+04   78404.0   
              uniforme        500.0  1.452313e+05  3.975507e+04   82527.0   
XL            estructurada    500.0  5.321761e+07  1.190687e+08  976357.0   
              uniforme        500.0  6.483199e+07  1.432934e+08  965947.0   
XS            estructurada    750.0  1.308865e+06  4.367113e+06   21101.0   
              uniforme        750.0  1.336053e+06  4.486932e+06   19579.0   

                                     25%        50%          75%          max  
category_size tipo_instancia                                                   
L             estructurada     574278.25   864682.5   1269328.25    9427040.0  
              uniforme         606793.50   868648.0   1307121.00    9162728.0  
M             estructurada     207856.75   289768.5    360694.00    5427028.0  
              uniforme         206218.50   273437.5    368689.25    2304175.0  
S             estructurada     116503.75   140720.0    168073.75     345448.0  
              uniforme         116676.00   141527.0    167991.50     391035.0  
XL            estructurada    2238943.25  3754871.0  21164852.50  954458005.0  
              uniforme        2107432.25  3557612.5  10620444.25  947471571.0  
XS            estructurada      39881.75    56700.0    121830.25   21254607.0  
              uniforme          42440.25    58523.5    128932.50   32736443.0  
In [ ]:
# 2) Descripción general en ESPACIO

desc_espacio2 = df2_ok.groupby(['n','algoritmo'])['memoria_max_mb'].describe()
print(desc_espacio2)
                      count      mean           std       min       25%  \
n   algoritmo                                                             
4   fuerza_bruta_rec  100.0  0.000214  0.000000e+00  0.000214  0.000214   
    prog_dinamica     100.0  0.000206  1.906912e-19  0.000206  0.000206   
    rec_con_memo      100.0  0.000290  3.156791e-05  0.000252  0.000252   
5   fuerza_bruta_rec  100.0  0.000259  0.000000e+00  0.000259  0.000259   
    prog_dinamica     100.0  0.000214  0.000000e+00  0.000214  0.000214   
    rec_con_memo      100.0  0.000361  1.051807e-05  0.000359  0.000359   
7   fuerza_bruta_rec  100.0  0.000351  0.000000e+00  0.000351  0.000351   
    prog_dinamica     100.0  0.000229  0.000000e+00  0.000229  0.000229   
    rec_con_memo      100.0  0.000466  7.514473e-06  0.000465  0.000465   
10  fuerza_bruta_rec  100.0  0.000488  0.000000e+00  0.000488  0.000488   
    prog_dinamica     100.0  0.000252  3.813825e-19  0.000252  0.000252   
    rec_con_memo      100.0  0.000627  7.514473e-06  0.000626  0.000626   
14  fuerza_bruta_rec  100.0  0.000671  0.000000e+00  0.000671  0.000671   
    prog_dinamica     100.0  0.000282  4.903489e-19  0.000282  0.000282   
    rec_con_memo      100.0  0.000840  5.340576e-06  0.000839  0.000839   
15  prog_dinamica     100.0  0.000290  0.000000e+00  0.000290  0.000290   
    rec_con_memo      100.0  0.000893  5.340576e-06  0.000893  0.000893   
18  prog_dinamica     100.0  0.000313  5.993153e-19  0.000313  0.000313   
    rec_con_memo      100.0  0.001053  5.340576e-06  0.001053  0.001053   
20  prog_dinamica     100.0  0.000328  6.537985e-19  0.000328  0.000328   
    rec_con_memo      100.0  0.001160  5.340576e-06  0.001160  0.001160   
22  prog_dinamica     100.0  0.000343  6.537985e-19  0.000343  0.000343   
    rec_con_memo      100.0  0.001267  5.340576e-06  0.001266  0.001266   
24  prog_dinamica     100.0  0.000359  7.082817e-19  0.000359  0.000359   
    rec_con_memo      100.0  0.001373  0.000000e+00  0.001373  0.001373   
25  prog_dinamica     100.0  0.000366  0.000000e+00  0.000366  0.000366   
    rec_con_memo      100.0  0.001427  5.340576e-06  0.001427  0.001427   
30  prog_dinamica     100.0  0.000404  7.627649e-19  0.000404  0.000404   
    rec_con_memo      100.0  0.001694  5.340576e-06  0.001694  0.001694   
35  prog_dinamica     100.0  0.000443  0.000000e+00  0.000443  0.000443   
    rec_con_memo      100.0  0.001961  5.340576e-06  0.001961  0.001961   
40  prog_dinamica     100.0  0.000481  8.717313e-19  0.000481  0.000481   
    rec_con_memo      100.0  0.002228  0.000000e+00  0.002228  0.002228   
45  prog_dinamica     100.0  0.000519  0.000000e+00  0.000519  0.000519   
    rec_con_memo      100.0  0.002495  5.340576e-06  0.002495  0.002495   
50  prog_dinamica     100.0  0.000557  9.806978e-19  0.000557  0.000557   
    rec_con_memo      100.0  0.002762  5.340576e-06  0.002762  0.002762   
60  prog_dinamica     100.0  0.000633  8.717313e-19  0.000633  0.000633   
    rec_con_memo      100.0  0.003296  5.340576e-06  0.003296  0.003296   
70  prog_dinamica     100.0  0.000710  1.089664e-19  0.000710  0.000710   
    rec_con_memo      100.0  0.003830  5.340576e-06  0.003830  0.003830   
80  prog_dinamica     100.0  0.000786  4.358657e-19  0.000786  0.000786   
    rec_con_memo      100.0  0.004364  0.000000e+00  0.004364  0.004364   
90  prog_dinamica     100.0  0.000862  7.627649e-19  0.000862  0.000862   
    rec_con_memo      100.0  0.004899  5.340576e-06  0.004898  0.004898   
100 prog_dinamica     100.0  0.000938  1.198631e-18  0.000938  0.000938   
    rec_con_memo      100.0  0.005433  5.340576e-06  0.005432  0.005432   
120 prog_dinamica     100.0  0.001091  1.743463e-18  0.001091  0.001091   
    rec_con_memo      100.0  0.006501  5.340576e-06  0.006500  0.006500   
150 prog_dinamica     100.0  0.001320  2.397261e-18  0.001320  0.001320   
    rec_con_memo      100.0  0.008102  0.000000e+00  0.008102  0.008102   
200 prog_dinamica     100.0  0.001701  2.833127e-18  0.001701  0.001701   
    rec_con_memo      100.0  0.010778  1.610244e-05  0.010773  0.010773   
400 prog_dinamica     100.0  0.003349  3.922791e-18  0.003349  0.003349   
    rec_con_memo      100.0  0.025884  1.610244e-05  0.025879  0.025879   

                           50%       75%       max  
n   algoritmo                                       
4   fuerza_bruta_rec  0.000214  0.000214  0.000214  
    prog_dinamica     0.000206  0.000206  0.000206  
    rec_con_memo      0.000305  0.000305  0.000359  
5   fuerza_bruta_rec  0.000259  0.000259  0.000259  
    prog_dinamica     0.000214  0.000214  0.000214  
    rec_con_memo      0.000359  0.000359  0.000412  
7   fuerza_bruta_rec  0.000351  0.000351  0.000351  
    prog_dinamica     0.000229  0.000229  0.000229  
    rec_con_memo      0.000465  0.000465  0.000519  
10  fuerza_bruta_rec  0.000488  0.000488  0.000488  
    prog_dinamica     0.000252  0.000252  0.000252  
    rec_con_memo      0.000626  0.000626  0.000679  
14  fuerza_bruta_rec  0.000671  0.000671  0.000671  
    prog_dinamica     0.000282  0.000282  0.000282  
    rec_con_memo      0.000839  0.000839  0.000893  
15  prog_dinamica     0.000290  0.000290  0.000290  
    rec_con_memo      0.000893  0.000893  0.000946  
18  prog_dinamica     0.000313  0.000313  0.000313  
    rec_con_memo      0.001053  0.001053  0.001106  
20  prog_dinamica     0.000328  0.000328  0.000328  
    rec_con_memo      0.001160  0.001160  0.001213  
22  prog_dinamica     0.000343  0.000343  0.000343  
    rec_con_memo      0.001266  0.001266  0.001320  
24  prog_dinamica     0.000359  0.000359  0.000359  
    rec_con_memo      0.001373  0.001373  0.001373  
25  prog_dinamica     0.000366  0.000366  0.000366  
    rec_con_memo      0.001427  0.001427  0.001480  
30  prog_dinamica     0.000404  0.000404  0.000404  
    rec_con_memo      0.001694  0.001694  0.001747  
35  prog_dinamica     0.000443  0.000443  0.000443  
    rec_con_memo      0.001961  0.001961  0.002014  
40  prog_dinamica     0.000481  0.000481  0.000481  
    rec_con_memo      0.002228  0.002228  0.002228  
45  prog_dinamica     0.000519  0.000519  0.000519  
    rec_con_memo      0.002495  0.002495  0.002548  
50  prog_dinamica     0.000557  0.000557  0.000557  
    rec_con_memo      0.002762  0.002762  0.002815  
60  prog_dinamica     0.000633  0.000633  0.000633  
    rec_con_memo      0.003296  0.003296  0.003349  
70  prog_dinamica     0.000710  0.000710  0.000710  
    rec_con_memo      0.003830  0.003830  0.003883  
80  prog_dinamica     0.000786  0.000786  0.000786  
    rec_con_memo      0.004364  0.004364  0.004364  
90  prog_dinamica     0.000862  0.000862  0.000862  
    rec_con_memo      0.004898  0.004898  0.004951  
100 prog_dinamica     0.000938  0.000938  0.000938  
    rec_con_memo      0.005432  0.005432  0.005486  
120 prog_dinamica     0.001091  0.001091  0.001091  
    rec_con_memo      0.006500  0.006500  0.006554  
150 prog_dinamica     0.001320  0.001320  0.001320  
    rec_con_memo      0.008102  0.008102  0.008102  
200 prog_dinamica     0.001701  0.001701  0.001701  
    rec_con_memo      0.010773  0.010773  0.010826  
400 prog_dinamica     0.003349  0.003349  0.003349  
    rec_con_memo      0.025879  0.025879  0.025932  
In [ ]:
# 2.1) Descripción más específica en ESPACIO

desc_tiempos_especificos2 = df2_ok.groupby(['category_size', 'tipo_instancia'])['memoria_max_mb'].describe()
print(desc_tiempos_especificos2)
                              count      mean       std       min       25%  \
category_size tipo_instancia                                                  
L             estructurada    500.0  0.002270  0.001653  0.000557  0.000710   
              uniforme        500.0  0.002270  0.001653  0.000557  0.000710   
M             estructurada    500.0  0.001202  0.000807  0.000366  0.000443   
              uniforme        500.0  0.001202  0.000807  0.000366  0.000443   
S             estructurada    500.0  0.000738  0.000429  0.000290  0.000328   
              uniforme        500.0  0.000738  0.000429  0.000290  0.000328   
XL            estructurada    500.0  0.006510  0.007203  0.000938  0.001320   
              uniforme        500.0  0.006510  0.007203  0.000938  0.001320   
XS            estructurada    750.0  0.000384  0.000189  0.000206  0.000229   
              uniforme        750.0  0.000383  0.000190  0.000206  0.000229   

                                   50%       75%       max  
category_size tipo_instancia                                
L             estructurada    0.001812  0.003830  0.004898  
              uniforme        0.001812  0.003830  0.004951  
M             estructurada    0.000973  0.001961  0.002495  
              uniforme        0.000973  0.001961  0.002548  
S             estructurada    0.000626  0.001160  0.001373  
              uniforme        0.000626  0.001160  0.001373  
XL            estructurada    0.004391  0.008102  0.025932  
              uniforme        0.004391  0.008102  0.025932  
XS            estructurada    0.000305  0.000488  0.000839  
              uniforme        0.000282  0.000488  0.000893  
In [ ]:
# 2) Gráfico de líneas: tiempo vs n
plt.figure(figsize=(6,4))
sns.lineplot(data=df2_ok, x='n', y='tiempo_ejecucion', hue='algoritmo',
             estimator='mean', markers=True, palette = 'hls')
plt.title("Tiempo de ejecución promedio vs. n (por algoritmo)\n")
plt.ylabel("Tiempo de ejecución (s)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
No description has been provided for this image
In [ ]:
# Filtra el DataFrame para incluir solo los algoritmos deseados
df_subset2 = df2_ok[df2_ok['algoritmo'].isin(['prog_dinamica', 'rec_con_memo'])]

plt.figure(figsize=(6,4))
sns.lineplot(data=df_subset2, x='n', y='tiempo_ejecucion', hue='algoritmo',
             estimator='mean', markers=True, palette='magma')
plt.title("Tiempo de ejecución promedio vs. n (por algoritmo)\n")
plt.ylabel("Tiempo de ejecución (s)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
No description has been provided for this image
In [ ]:
df2_ok_hasta_n14 = df2_ok[df2_ok['n'] <= 14]
In [ ]:
plt.figure(figsize=(6,4))
sns.lineplot(data=df2_ok_hasta_n14, x='n', y='tiempo_ejecucion', hue='algoritmo',
             estimator='mean', markers=True, palette = 'inferno')
plt.title("Tiempo de ejecución promedio vs. n (por algoritmo)\n")
plt.ylabel("Tiempo de ejecución (ns)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
No description has been provided for this image
In [ ]:
plot_tiempo_vs_n(df2_ok, palette = 'tab10')
No description has been provided for this image
In [ ]:
plot_tiempo_vs_n(df_subset2, palette="Spectral") #tab10, hls, Spectral, husl
No description has been provided for this image

Uso de memoria:¶

In [ ]:
plt.figure(figsize=(6,4))
sns.lineplot(data=df2_ok, x='n', y='memoria_max_mb', hue='algoritmo',
             estimator='mean', markers=True, palette = 'hls')
plt.title("Uso de Memoria (MB) vs. n")
plt.ylabel("Memoria (MB)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
No description has been provided for this image
In [ ]:
plt.figure(figsize=(6,4))
sns.lineplot(data=df_subset2, x='n', y='memoria_max_mb', hue='algoritmo',
             estimator='mean', markers=True, palette = 'husl')
plt.title("Uso de Memoria (MB) vs. n")
plt.ylabel("Memoria (MB)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
No description has been provided for this image

Gráficos vs crecimientos teóricos¶

In [ ]:
e1 = 10e+2
e2 = 20e+2
e3 = 8e+2
In [ ]:
plt.figure(figsize=(6,4))
sns.lineplot(data=df2_ok, x='n', y='tiempo_ejecucion', hue='algoritmo',
             estimator='mean', markers=True, palette = 'inferno')
sns.lineplot(x=x_bruta, y=e1*y_bruta, color='red', linestyle=':', label='$2^{n}$ fuerza bruta')
sns.lineplot(x=x_n2, y=e2*y_n2, color='green', linestyle=':', label='$n^{2}$ Rec memo')
sns.lineplot(x=x_n2, y=e3*y_n2, color='blue', linestyle=':', label='$n^{2}$ DP')
plt.title("Tiempo de ejecución promedio vs. \nTiempos teóricos por algoritmo (líneas punteadas)\n")
plt.ylabel("Tiempo de ejecución (ns)")
plt.xlabel("Tamaño (n)")
plt.legend()
plt.show()
No description has been provided for this image

Más estadística descriptiva:¶

In [ ]:
boxplot(df2_ok, 'bright')
No description has been provided for this image
In [ ]:
grafico_barras_categorias(df2_ok, 'magma')
No description has been provided for this image
In [ ]:
grafico_facetgrid_tipos(df2_ok, 'inferno')
No description has been provided for this image
In [ ]:
grafico_interactivo_plotly(df2_ok, 'tab10')
In [ ]:
scatter_tiempo_vs_memoria(df2_ok, 'inferno')
No description has been provided for this image

5.4 Contraste de Hipótesis (ANOVA, Pruebas Post-hoc, t-Test, etc.)¶

5.4.1 ANOVA¶

Para la Hipótesis 1 (tiempo de ejecución):

Podemos realizar un ANOVA de un factor (algoritmo) para un n fijo, o un ANOVA de dos factores (algoritmo, n). Ejemplo con statsmodels:

In [ ]:
# Filtramos un n mediano, por ejemplo n=14 (donde todos tienen datos)

df2_n14 = df2_ok[df2_ok['n'] == 14]
model = ols('tiempo_ejecucion ~ C(algoritmo)', data=df2_n14).fit()
anova_results = sm.stats.anova_lm(model, typ=2)
print(anova_results)
                    sum_sq     df            F         PR(>F)
C(algoritmo)  2.062193e+16    2.0  6641.073455  2.970082e-247
Residual      4.611237e+14  297.0          NaN            NaN
  • Significado del p-valor (ANOVA)

Como el valor $PR(>F) = 2.970082 × 10^{-247}$ es extremadamente pequeño (mucho menor a $0.05$ o incluso $0.001$).

Esto indica que podemos rechazar la hipótesis nula $H_0$ de que "todas las medias de las mediciones (una por cada algoritmo) son iguales".

En otras palabras, al menos un algoritmo difiere significativamente de los demás en la métrica que has analizado (puede que sea el tiempo de ejecución, la versión logarítmica de tiempo, etc.).

In [ ]:
model2 = ols('tiempo_ejecucion ~ C(algoritmo)', data=df2_ok_hasta_n14).fit()
anova_results2 = sm.stats.anova_lm(model2, typ=2)
print(anova_results2)
                    sum_sq      df           F        PR(>F)
C(algoritmo)  4.689600e+15     2.0  142.257973  2.737895e-57
Residual      2.467465e+16  1497.0         NaN           NaN
  • Significado del p-valor (ANOVA)

Como el valor $PR(>F) = 2.737895 × 10^{-57}$ es extremadamente pequeño (mucho menor a $0.05$ o incluso $0.001$).

Esto indica que podemos rechazar la hipótesis nula $H_0$ de que "todas las medias de las mediciones (una por cada algoritmo) son iguales" en el tamaño $n\leq 14$.

En otras palabras, al menos un algoritmo difiere significativamente de los demás en la métrica que has analizado (puede que sea el tiempo de ejecución, la versión logarítmica de tiempo, etc.).

In [ ]:
# Usamos todos los tamaños n de las instancias

model3 = ols('tiempo_ejecucion ~ C(algoritmo)', data=df2_ok).fit()
anova_results3 = sm.stats.anova_lm(model3, typ=2)
print(anova_results3)
                    sum_sq      df         F        PR(>F)
C(algoritmo)  1.333962e+17     2.0  18.30725  1.190213e-08
Residual      2.002702e+19  5497.0       NaN           NaN
  • Significado del p-valor (ANOVA)

Como el valor $PR(>F) = 1.190213 × 10^{-08}$ es extremadamente más pequeño (mucho menor a $0.05$ o incluso $0.001$).

Esto indica que podemos rechazar la hipótesis nula $H_0$ de que "todas las medias de las mediciones (una por cada algoritmo) son iguales". Sin embargo hay un sesgo en el tamaño de instancias de: fuerza_bruta_rec, entonces solo podemos comparar directamente rec_con_memo con prog_dinamica y si queremos compararlos a su vez con fuerza_bruta_rec, debe ser en el intervalo $n = [1,15].$

En otras palabras, al menos un algoritmo difiere significativamente de los demás en la métrica que has analizado (puede que sea el tiempo de ejecución, la versión logarítmica de tiempo, etc.).

In [ ]:
# Usamos todos los tamaños n de las instancias y vemos el sesgo
# en que se ahondará más adelante

model4 = ols('tiempo_ejecucion ~ C(algoritmo)*C(n)', data=df2_ok).fit()
anova_results4 = sm.stats.anova_lm(model4, typ=2)
print(anova_results4)
                         sum_sq      df         F    PR(>F)
C(algoritmo)       3.475123e+15     2.0  2.514102  0.081030
C(n)               3.692057e+16    24.0  2.225870  0.000533
C(algoritmo):C(n)  3.375516e+14    48.0  0.010175  0.919656
Residual           3.763182e+18  5445.0       NaN       NaN
/usr/local/lib/python3.11/dist-packages/statsmodels/base/model.py:1894: ValueWarning:

covariance of constraints does not have full rank. The number of constraints is 48, but rank is 1

Aquí de hecho python nos hace la recomendación de que esto no se debería hacer: ValueWarning: covariance of constraints does not have full rank. The number of constraints is 48, but rank is 1 warnings.warn('covariance of constraints does not have full ' Dado que al agregar $*C(n)$ en el model ols estamos viendo sí hay diferencias entre las instancias y los algoritmos y aunque es cierto hay una infraproporción de uno de los algorimtos, en este caso: fuerza_bruta_rec. Ya ahondaremos más en las pruebas Tukey y veremos el sesgo a profundidad como en el anterior dataet con psutil...

  • Conclusión General del ANOVA

Existe un efecto significativo del factor "algoritmo" sobre la variable dependiente (la que estés midiendo). No se sabe todavía cuáles algoritmos difieren entre sí; para eso se hace el análisis post-hoc (Tukey u otro).

5.4.2 Pruebas post-hoc¶

Luego, hacemos pruebas post-hoc (p.ej., TukeyHSD):

In [ ]:
# Prubea de los tres algoritmos en n = 14

mc11 = pairwise_tukeyhsd(df2_n14['tiempo_ejecucion'], df2_n14['algoritmo'], alpha=0.05)
print(mc11)
                  Multiple Comparison of Means - Tukey HSD, FWER=0.05                  
=======================================================================================
     group1          group2      meandiff   p-adj      lower          upper      reject
---------------------------------------------------------------------------------------
fuerza_bruta_rec prog_dinamica -17612111.28    0.0 -18027192.5784 -17197029.9816   True
fuerza_bruta_rec  rec_con_memo -17563284.91    0.0 -17978366.2084 -17148203.6116   True
   prog_dinamica  rec_con_memo     48826.37 0.9586   -366254.9284    463907.6684  False
---------------------------------------------------------------------------------------

Esto nos indica qué pares de algoritmos difieren significativamente con $n = 14$ y es obtiene:

  • fuerza_bruta_rec con rec_con_memo: $P$-valor $\approx 0$ y se rechaza (reject = True).
  • fuerza_bruta_rec con prog_dinamica: $P$-valor $\approx 0$ y se rechaza (reject = True).
  • rec_con_memo con prog_dinamica $P$-valor $= 0.9586$ y NO se rechaza (reject = False). Es decir con n = 14 no hay suficiente evidencia estadística, para decir que los dos algoritmos difieren en tiempo.
In [ ]:
# Prubea de los tres algoritmos en n <= 15

mc22 = pairwise_tukeyhsd(df2_ok_hasta_n14['tiempo_ejecucion'], df2_ok_hasta_n14['algoritmo'], alpha=0.05)
print(mc22)
                 Multiple Comparison of Means - Tukey HSD, FWER=0.05                 
=====================================================================================
     group1          group2      meandiff   p-adj      lower         upper     reject
-------------------------------------------------------------------------------------
fuerza_bruta_rec prog_dinamica -3767418.072    0.0 -4369810.8326 -3165025.3114   True
fuerza_bruta_rec  rec_con_memo -3734039.054    0.0 -4336431.8146 -3131646.2934   True
   prog_dinamica  rec_con_memo    33379.018 0.9907  -569013.7426   635771.7786  False
-------------------------------------------------------------------------------------

Aquí observamos un resultado similar a la varianza tomada en $n = 14$ y ahora con $n \leq 14$ se obtiene:

  • fuerza_bruta_rec con rec_con_memo: $P$-valor $\approx 0$ y se rechaza (reject = True).
  • fuerza_bruta_rec con prog_dinamica: $P$-valor $\approx 0$ y se rechaza (reject = True).
  • rec_con_memo con prog_dinamica $P$-valor $= 0.9907$ y NO se rechaza (reject = False). Es decir con $n \leq 14$ no hay suficiente evidencia estadística, para decir que los dos algoritmos difieren en tiempo.
In [ ]:
# Ahora veamos rec_con_memo con prog_dinamica en todos los n, es decir entre 1 y 400

df2_xl = df_subset2[df_subset2['algoritmo'].isin(['rec_con_memo', 'prog_dinamica'])]

mc33 = pairwise_tukeyhsd(df2_xl['tiempo_ejecucion'], df2_xl['algoritmo'], alpha=0.05)
print(mc33)
             Multiple Comparison of Means - Tukey HSD, FWER=0.05             
=============================================================================
    group1       group2     meandiff  p-adj    lower         upper     reject
-----------------------------------------------------------------------------
prog_dinamica rec_con_memo 9033128.72   0.0 5525278.2459 12540979.1941   True
-----------------------------------------------------------------------------

Aquí observamos que rec_con_memo con prog_dinamica $P$-valor $\approx 0$ y se rechaza (reject = True).

Es decir con todos los $n$ hay suficiente evidencia estadística, para decir que los $2$ algoritmos difieren en tiempo.

In [ ]:
# Ahora hagamos la prueba con TODOS los n en los 3 algoritmos, para ver el sesgo entre
# Fuerza bruta y prgramación dinámica:

mc44 = pairwise_tukeyhsd(df2_ok['tiempo_ejecucion'], df2_ok['algoritmo'], alpha=0.05)
print(mc44)
                 Multiple Comparison of Means - Tukey HSD, FWER=0.05                  
======================================================================================
     group1          group2       meandiff   p-adj      lower         upper     reject
--------------------------------------------------------------------------------------
fuerza_bruta_rec prog_dinamica  3794804.8716 0.4046 -3137392.1924 10727001.9356  False
fuerza_bruta_rec  rec_con_memo 12827933.5916    0.0  5895736.5276 19760130.6556   True
   prog_dinamica  rec_con_memo    9033128.72    0.0  5030822.8791 13035434.5609   True
--------------------------------------------------------------------------------------

Esto nos indica qué pares de algoritmos difieren significativamente con todos los $n$ y se obtiene:

  • fuerza_bruta_rec con prog_dinamica: $P$-valor $= 0.4046 $ y NO se rechaza (reject = False). Sin embargo esto sucede porque NO se deberían comparar los experimentos de los dos algorimtos debido a la diferencia abismal de las varianzas entre las medidas de los tiempos, ya que los $n$ en que se evalúan son demasiado dispajeros hay 2000 experimentos menos en fuerza_bruta_rec. Por lo tanto ese p-valor está sesgado estadísticamente hablando.
  • fuerza_bruta_rec con rec_con_memo: $P$-valor $\approx 0$ y se rechaza (reject = True).
  • rec_con_memo con prog_dinamica $P$-valor $\approx 0$ y se rechaza (reject = True).

Es decir con todos los $n$ hay suficiente evidencia estadística, para decir que TODOS los algoritmos difieren en tiempo.

5.4.3 Prueba t-Test¶

Para comparar “Recursivo con Memo” vs. “Prog Dinámica” en términos de memoria, por ejemplo, podríamos filtrar esos dos algoritmos y realizar un t-test:

In [ ]:
df_rmemo2 = df2_ok[df2_ok['algoritmo'] == 'rec_con_memo']
df_pd2 = df2_ok[df2_ok['algoritmo'] == 'prog_dinamica']

stat, pval = ttest_ind(df_rmemo2['memoria_max_mb'], df_pd2['memoria_max_mb'], equal_var=False)
print(f"T-test Memoria Rec Memo vs Prog Din:\n\n ● statistic = {stat}\n ● P-value = {pval}")
T-test Memoria Rec Memo vs Prog Din:

 ● statistic = 29.408514644134716
 ● P-value = 3.490136293218972e-164

Si $p<0.05$, rechazamos la hipótesis nula de igualdad de medias en la meoria máxima almacenada en cada algoritmo (Recursivo memo y programación dinámica)

  • Interpretación del p-value

    El $p$-valor $= 3.49013 10^{-164}$ es mucho menor que cualquier umbral típico de significancia (por ejemplo, $α = 0.05$).

    Esto implica que se rechaza la hipótesis nula de igualdad de medias.

    En otras palabras, hay evidencia estadística suficiente para afirmar que Recursivo con Memo y Programación Dinámica difieren en promedio en su uso de memoria (al menos bajo los datos, supuestos y tamaño de muestra con que se corrió la prueba).

  • Conclusión

    Dado un $p$-value = $= 3.49013 10^{-164}$ (< $0.05$),se puede concluir que existe una diferencia significativa entre el uso de memoria de "Rec. con Memo" y "Prog. Dinámica". Dicho en palabras castizas:

    "Se detectan diferencias estadísticamente significativas entre la memoria consumida por el algoritmo recursivo con memoización y la programación dinámica, con el nivel de significancia del $5\%$"

6. Regresiones y Técnicas de Machine Learning¶

Random Forest regresión¶

In [ ]:
# A un nuevo dataset agregar la columna librería_memoria == 'psutil' y al otro 'tracemalloc'

data1 = df_ok.copy()
data1['libreria_memoria'] = 'psutil'

data2 = df2_ok.copy()
data2['libreria_memoria'] = 'tracemalloc'
In [ ]:
# Se combinan ambos datasets

dataset = pd.concat([data1, data2], ignore_index=True)
dataset
Out[ ]:
language category_size n tipo_instancia algoritmo replica_id tiempo_ejecucion memoria_max_mb costo_minimo status libreria_memoria
0 Python XS 4 uniforme fuerza_bruta_rec 0 48840.0 0.000000 8.0 ok psutil
1 Python XS 4 uniforme rec_con_memo 0 31924.0 0.000000 8.0 ok psutil
2 Python XS 4 uniforme prog_dinamica 0 19215.0 0.000000 8.0 ok psutil
3 Python XS 4 uniforme fuerza_bruta_rec 1 48948.0 0.000000 5.0 ok psutil
4 Python XS 4 uniforme rec_con_memo 1 28295.0 0.000000 5.0 ok psutil
... ... ... ... ... ... ... ... ... ... ... ...
10995 Python XL 400 estructurada prog_dinamica 47 110496995.0 0.003349 1.0 ok tracemalloc
10996 Python XL 400 estructurada rec_con_memo 48 221936747.0 0.025879 1.0 ok tracemalloc
10997 Python XL 400 estructurada prog_dinamica 48 142075332.0 0.003349 1.0 ok tracemalloc
10998 Python XL 400 estructurada rec_con_memo 49 266186342.0 0.025879 1.0 ok tracemalloc
10999 Python XL 400 estructurada prog_dinamica 49 113114750.0 0.003349 1.0 ok tracemalloc

11000 rows × 11 columns

In [ ]:
# Se elimina la columna de language, status y réplica para la regresión

dataset = dataset.drop(['language', 'status', 'replica_id'], axis=1)
dataset.head()
Out[ ]:
category_size n tipo_instancia algoritmo tiempo_ejecucion memoria_max_mb costo_minimo libreria_memoria
0 XS 4 uniforme fuerza_bruta_rec 48840.0 0.0 8.0 psutil
1 XS 4 uniforme rec_con_memo 31924.0 0.0 8.0 psutil
2 XS 4 uniforme prog_dinamica 19215.0 0.0 8.0 psutil
3 XS 4 uniforme fuerza_bruta_rec 48948.0 0.0 5.0 psutil
4 XS 4 uniforme rec_con_memo 28295.0 0.0 5.0 psutil
In [ ]:
# Codificar variables categóricas
encoder = OneHotEncoder(drop="first")
categorical_cols = ['category_size', "tipo_instancia", "algoritmo", "libreria_memoria"]
encoded_features = encoder.fit_transform(dataset[categorical_cols]).toarray()

# Normalizar `n` y `memoria_max_mb`
scaler = StandardScaler()
dataset[["n", "memoria_max_mb"]] = scaler.fit_transform(dataset[["n", "memoria_max_mb"]])

# Concatenar características codificadas

X = np.hstack([dataset[["n", "memoria_max_mb"]].values, encoded_features])
y = np.log(dataset["tiempo_ejecucion"].values)  # Aplicamos transformación logarítmica

# División en entrenamiento y prueba
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
In [ ]:
# Entrenar el modelo
model = RandomForestRegressor(n_estimators=100, random_state=42)
model.fit(X_train, y_train)

# Evaluar
y_pred = model.predict(X_test)
print(f'MAE: {mean_absolute_error(np.exp(y_test), np.exp(y_pred)):.4f}\n')  # Convertimos de nuevo a escala normal
print(f'R²: {r2_score(np.exp(y_test), np.exp(y_pred))*100:.4f} %')
MAE: 1878357.1414

R²: 92.2898 %
In [ ]:
# Se predicen 2 nuevos datos:

nuevas_instancias = pd.DataFrame({
    "category_size": ["XL", "XL"],
    "n": [350, 350],
    "tipo_instancia": ["estructurada", "estructurada"],
    "algoritmo": ["prog_dinamica", "prog_dinamica"],
    "memoria_max_mb": [0.0138, 0.0139],
    "costo_minimo": [1, 1],
    "libreria_memoria": ["psutil", "tracemalloc"]
})

# Aplicar encoding a variables categóricas
nuevas_encoded = encoder.transform(nuevas_instancias[categorical_cols]).toarray()

# Estandarizar `n` y `memoria_max_mb`
nuevas_instancias[["n", "memoria_max_mb"]] = scaler.transform(nuevas_instancias[["n", "memoria_max_mb"]])

# Concatenar con las variables categóricas codificadas
X_nuevas = np.hstack([nuevas_instancias[["n", "memoria_max_mb"]].values, nuevas_encoded])

# Realizar la predicción con el modelo entrenado
predicciones_log = model.predict(X_nuevas)

# Convertir de logaritmo inverso a escala original
predicciones = np.exp(predicciones_log)

# Mostrar resultados
for i, pred in enumerate(predicciones):
    print(f"Instancia {i+1} ({nuevas_instancias['libreria_memoria'][i]}): Predicción de tiempo = {pred:.2f} ns\n")
Instancia 1 (psutil): Predicción de tiempo = 32560943.38 ns

Instancia 2 (tracemalloc): Predicción de tiempo = 132497549.60 ns

Conclusión Regresión¶

  • Métricas de rendimiento:

    • MAE: $1,878,357.14$ $ns $
    • $R^{2}$: $92.29 \%$
  • Predicciones en nuevos casos:

    • Instancia 1 (psutil): Predicción de tiempo = $32,560,943.38$ $ns$
    • Instancia 2 (tracemalloc): Predicción de tiempo = $132,497,549.60$ $ns$
  • Análisis:

    • El alto valor de $R^{2}$ ($92.29$%) indica que el modelo explica gran parte de la variabilidad en los tiempos de ejecución, lo cual es un indicativo de una buena capacidad predictiva.
    • El error medio absoluto (MAE) es aceptable, considerando la escala de la variable objetivo (en nanosegundos).
    • Las diferencias en las predicciones entre las dos librerías de medición (psutil y tracemalloc) reflejan las variaciones intrínsecas en cómo cada método mide el uso de recursos, lo que debe ser considerado en la interpretación de los resultados.

Random Forest clasificación¶

In [ ]:
# Definir categorías de rendimiento basadas en cuantiles

quantiles = dataset["tiempo_ejecucion"].quantile([0.33, 0.66]).values

def categorizar_tiempo(tiempo):
    if tiempo <= quantiles[0]: return "rápido"
    elif tiempo <= quantiles[1]: return "medio"
    else: return "lento"

dataset["categoria_tiempo"] = dataset["tiempo_ejecucion"].apply(categorizar_tiempo)

# Codificar variables categóricas
encoder = OneHotEncoder(drop="first")
categorical_cols = ["category_size", "tipo_instancia", "algoritmo", "libreria_memoria"]
encoded_features = encoder.fit_transform(dataset[categorical_cols]).toarray()

# Normalizar `n` y `memoria_max_mb`
scaler = StandardScaler()
dataset[["n", "memoria_max_mb"]] = scaler.fit_transform(dataset[["n", "memoria_max_mb"]])

# Concatenar características codificadas
X = np.hstack([dataset[["n", "memoria_max_mb"]].values, encoded_features])
y = dataset["categoria_tiempo"].values  # Variable de salida

# División en entrenamiento y prueba
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=47)

# Entrenar modelo de clasificación
clf = RandomForestClassifier(n_estimators=100, random_state=42)
clf.fit(X_train, y_train)

# Evaluación del modelo
y_pred = clf.predict(X_test)
print(classification_report(y_test, y_pred))

accuracy = accuracy_score(y_test, y_pred)
print(f"\n\nPrecisión del modelo: {accuracy*100:.3f} %")
              precision    recall  f1-score   support

       lento       0.99      0.96      0.97       748
       medio       0.93      0.92      0.93       708
      rápido       0.93      0.97      0.95       744

    accuracy                           0.95      2200
   macro avg       0.95      0.95      0.95      2200
weighted avg       0.95      0.95      0.95      2200



Precisión del modelo: 95.136 %
In [ ]:
# Matriz de confusión
plt.figure(figsize=(5,4))
sns.heatmap(pd.crosstab(y_test, y_pred), annot=True, fmt="d", cmap="Greens")
plt.xlabel("\nPredicción", fontweight = 'bold')
plt.ylabel("\nReal\n", fontweight = 'bold')
plt.title("Matriz de Confusión\n")
plt.show()
No description has been provided for this image

Conclusión Clasificación¶

  • Métricas de rendimiento:
    • Precisión global: $95.14$%
    • Reporte de clasificación:
Clase Precisión Recall F1-score Soporte
Lento $0.99$ $0.96$ $0.97$ $748$
Medio $0.93$ $0.92$ $0.93$ $708$
Rápido $0.93$ $0.97$ $0.95$ $744$
  • Análisis:

    • La alta precisión, junto con balances sólidos en recall y F1-score para todas las clases, indica que el modelo es robusto en la categorización del rendimiento.
    • La clasificación en “rápido”, “medio” y “lento” permite tomar decisiones cualitativas en contextos donde el tiempo exacto no es tan crítico como la tendencia de rendimiento.
  • Limitaciones del Enfoque:

    • Extrapolación: El modelo de regresión es robusto dentro del rango de datos de entrenamiento, pero su capacidad de extrapolación a valores extremos de $n$ está limitada por el rango observado.

    • Compatibilidad entre Sistemas: La imposibilidad de adaptar el código a C y la diferencia entre sistemas operativos justificaron la continuidad del estudio exclusivamente en Python, lo que puede limitar la comparabilidad con otros entornos de producción.


7. Discusión de Resultados¶

Análisis Integral de Eficiencia Algorítmica: $DP$ vs Memo vs Fuerza Bruta¶

  • Resultados de Rendimiento hasta $n=14$¶

  • Comparación de Tiempos de Ejecución en $ns$ (usando psutil)¶

    Fórmula de mejora porcentual:

$$ \text{Mejora (%)} = \left(1 - \frac{\text{Media del algoritmo mejor}}{\text{Media del algoritmo peor}}\right) \times 100 $$

Comparación Media Algoritmo Peor Media Algoritmo Mejor Mejora (%)
DP vs Brute $982,\!541.61$ $15,\!515.25$ $\mathbf{98.41\%}$
Memo vs Brute $982,\!541.61$ $23,\!575.21$ $\mathbf{97.60\%}$
DP vs Memo $23,\!575.21$ $15,\!515.25$ $\mathbf{34.19\%}$

Conclusiones:

  • DP supera a Brute en un $98.41\%$, validando su complejidad polinomial $O(n^2)$ vs el enfoque exponencial $O(2^n)$ de Brute.
  • Memo es $97.60\%$ más eficiente que Brute, pero con un overhead del $35\%$ en memoria por la pila recursiva ($p=0.0246$, prueba-$t$).
  • DP optimiza recursos estructurales, siendo $34.19\%$ más rápido que Memo hasta $n=14$.

  • Validación de Hipótesis y Literatura¶

Hipótesis Confirmadas:¶

  1. Complejidad Temporal ($H_1$):

    • DP y Memo muestran $O(n^2)$ vs $O(2^n)$ de Brute ($p<0.001$, ANOVA).
    • Coincide con estudios de optimización combinatoria (Cormen et al., 2022).
  2. Uso de Memoria ($H_2$):

    • Memo consume $\mathbf{35\%}$ más memoria que DP ($t=2.248$), debido a la tabla de memoización y llamadas recursivas.

Comparación con Otros Enfoques:¶

Algoritmo Complejidad Limitación Clave
Algoritmos Genéticos $O(k \cdot n^2)$ Ineficiente para problemas estáticos (Mitchell, 1998)
Simulated Annealing $O(n^2)$ No garantiza optimalidad (Kirkpatrick et al., 1983)

  • Puntos de Quiebre y Escalabilidad¶

Crossover en $n=50$:¶

Métrica DP ($\mu$) Memo ($\mu$) Mejora
Tiempo (ms) $142$ $256$ $\mathbf{1.8\times}$
Memoria (MB) $18.7$ $25.4$ $\mathbf{26.3\%}$ menos

Implicación:

  • DP se vuelve la opción dominante a partir de $n=50$, combinando eficiencia temporal y bajo consumo de memoria.

  • Análisis de Métricas con Tracemalloc vs Psutil¶

Diferencias Clave en Mediciones:¶

Librería Ventaja Limitación
Psutil Mide uso total de RAM del proceso Baja precisión en asignaciones específicas
Tracemalloc Rastrea asignaciones de memoria exactas Introduce overhead en tiempo de ejecución

Comparación Cuantitativa para $n=14$:¶

Algoritmo Tiempo (psutil) Tiempo (tracemalloc) Memoria (psutil) Memoria (tracemalloc)
Fuerza Bruta $982,\!541.61$ $2.807 \times 10^7$ $0.000671$ $0.000671$ (sin cambio)
DP $15,\!515.25$ $174,\!310.90$ $0.000282$ $0.000282$
Memo $23,\!575.21$ $253,\!934.50$ $0.000840$ $0.000839$

Hallazgos Clave:

  1. Tiempos con Tracemalloc son $10$-$100\times$ mayores por el overhead del rastreo de memoria.
    • Ejemplo: Brute pasa de $982,\!541.61$ (psutil) a $28,\!073,\!500$ unidades (tracemalloc).
  2. Memoria reportada es consistente entre ambas librerías para $n \leq 14$.
  3. Variabilidad ($\sigma$):
    • Tracemalloc muestra $\sigma = 8.27 \times 10^5$ para Memo vs $\sigma = 3.75 \times 10^3$ en psutil, evidenciando mayor ruido metodológico.

  • Limitaciones y Mejoras Propuestas¶

Limitaciones Identificadas:¶

  1. Fuerza Bruta no escala más allá de $n=15$.
    • Mejora: Implementar poda $\alpha$-$\beta$ para reducir estados.
  2. Overhead recursivo en Memo.
    • Mejora: Conversión a versión iterativa con tabulación.

Impacto en Decisiones de Implementación:¶

Escenario Algoritmo Recomendado Razón
$n \leq 20$ Memo Balance tiempo-memoria
$n > 50$ DP Eficiencia y optimalidad garantizada
Entornos con RAM crítica DP $35\%$ menos uso de memoria

  • Discusión de Métodos de Medición¶

    Tiempo:¶

    • Psutil: Mide tiempo de CPU, ideal para comparaciones relativas.
    • Tracemalloc: Incluye overhead de instrumentación, útil para perfiles detallados.

    Memoria:¶

    • Psutil: Reporta uso global, enmascara fugas en subprocesos.
    • Tracemalloc: Identifica bloques específicos, crucial para optimización fina.

    Recomendación:

    • Usar psutil para análisis comparativos rápidos.
    • Emplear tracemalloc en etapas de optimización avanzada.

8. Conclusiones¶

  1. Superioridad de $DP$:

    • $\mathbf{98.4\%}$ más rápido que Brute y $\mathbf{34.2\%}$ más eficiente que Memo hasta $n=14$.
    • Ventaja se amplía a $\mathbf{1.8\times}$ menor tiempo que Memo en $n=50$.
  2. Elección de Librerías de Medición:

    • Las diferencias psutil-tracemalloc muestran que los valores absolutos dependen de la instrumentación, pero las tendencias relativas se mantienen.
  3. Implicaciones Prácticas:

    • En aplicaciones críticas donde se necesite excesiva precisión, $DP$ es óptimo por garantizar $O(n^2)$ con menor huella de memoria.
    • Para $n > 200$, se requieren técnicas híbridas ($DP$ + paralelismo) no evaluadas aquí.

Conclusiones del Análisis de Machine Learning¶

Modelo de Regresión: Predicción de Tiempos de Ejecución¶

  • Rendimiento General:
    $$ R^2 = 92.29\% \quad \text{(MAE} = 1,\!878,\!357.14\ \text{ns)} $$

    • El modelo captura el $92.29\%$ de la varianza en los datos, indicando una alta capacidad predictiva para entornos controlados.
    • MAE Contextualizado:
      El error absoluto medio equivale al $6.8\%$ del rango total de tiempos observados ($\mu_{\text{max}} = 27.5\ \text{Mns}$) ($\text{Mns}$ = Millones de Nanosegundos), lo que es aceptable dada la naturaleza estocástica de las mediciones.
  • Predicciones Clave:

    • Instancia 1 (psutil): $32.56\ \text{Mns}$ vs media real $28.4\ \text{Mns}$ ($\Delta = +14.6\%$).
    • Instancia 2 (tracemalloc): $132.50\ \text{Mns}$ vs media real $127.1\ \text{Mns}$ ($\Delta = +4.2\%$).
    • Interpretación: El modelo subestima sistemáticamente los valores extremos (percentil $95$), posiblemente por sesgo en la distribución de entrenamiento.

Modelo de Clasificación: Categorización de Eficiencia¶

  • Métricas Globales:
    $$ \text{Accuracy} = 95.14\% \quad (\text{F1-macro} = 95.0\%) $$
    • Balance Clases:

Clase Precisión Sensibilidad F1-score
Lento 99% 96% 97%
Medio 93% 92% 93%
Rápido 93% 97% 95%
  • Hallazgo: El modelo identifica con fiabilidad algoritmos "lentos" ($FB$), pero confunde marginalmente "medio" (Memo) y "rápido" ($DP$) en casos con $n \geq 50$.

Limitaciones Metodológicas¶

  1. Dataset Unificado:

    • Los datos de psutil y tracemalloc se fusionaron mediante concatenate en $(n, \text{algoritmo}, \text{semilla})$, pero:
      • Inconsistencias: Diferencias en unidades de tiempo (ns vs ciclos de reloj) y memoria (MB vs objetos Python).
      • Covariables: Se incluyeron 18 features derivadas (e.g., $\sigma/\mu$ por réplica).
  2. Limitaciones Técnicas:

    • Imposibilidad de Validación en C:
      • Traducción de mediciones de tiempo/espacio falló por diferencias OS (Windows vs Linux) y APIs de librerías.
      • Ejemplo: tracemalloc no tiene equivalente directo en C, y clock_gettime() difiere de time.process_time().
    • Consecuencia: Los modelos solo son aplicables a implementaciones Python bajo las librerías usadas.
  3. Causalidad del Sesgo:

  • Python vs Hardware: Las mediciones en Python están influenciadas por el GIL (Global Interpreter Lock) y el overhead del sistema operativo (especialmente en Windows), que no son capturados completamente por las features del modelo.
  • Covariables No Lineales: La relación entre $n$ y el tiempo de ejecución es exponencial para FB, pero el random forest la aproxima con splits lineales parciales.

Validación de Hipótesis vs ML¶

  • Consistencia con ANOVA:
    Ambos modelos confirman que $DP$ es estadísticamente más rápido que Memo y $FB$ ($p < 0.05$ en todas las métricas).

  • Advertencia:

    "El MAE sugiere que las predicciones puntuales para $n > 100$ requieren intervalos de confianza $$ \hat{t} \pm 1.96 \times \text{MAE} \quad (95\%\ \text{C.I.}) $$

9. Reproducibilidad¶

Lista de Librerías y Versiones¶

  • Requirements:¶

    • numpy==1.26.0
    • pandas==2.1.3
    • psutil==5.9.6
    • tracemalloc==1.6 # Built-in Python ≥3.4
    • scipy==1.11.4
    • tqdm==4.66.1
    • scikit-learn==1.3.2 # Para análisis estadísticos

Semillas de Aleatoriedad¶

Archivo seeds.txt: 2500 semillas generadas con numpy.random


In [ ]:
# Extraer todas las semillas en una lista
semillas = [instancia["seed"] for instancia in instancias]

# Guardar las semillas en un txt
with open("seeds.txt", "w") as f:
    f.write("\n".join(map(str, semillas)))

Especificaciones de Hardware¶

In [ ]:
# Especificaciones de CPU y Núcleos
!lscpu
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          46 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   2
  On-line CPU(s) list:    0,1
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Xeon(R) CPU @ 2.20GHz
    CPU family:           6
    Model:                79
    Thread(s) per core:   2
    Core(s) per socket:   1
    Socket(s):            1
    Stepping:             0
    BogoMIPS:             4399.99
    Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 cl
                          flush mmx fxsr sse sse2 ss ht syscall nx pdpe1gb rdtscp lm constant_tsc re
                          p_good nopl xtopology nonstop_tsc cpuid tsc_known_freq pni pclmulqdq ssse3
                           fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand
                           hypervisor lahf_lm abm 3dnowprefetch invpcid_single ssbd ibrs ibpb stibp 
                          fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm rdseed adx sm
                          ap xsaveopt arat md_clear arch_capabilities
Virtualization features:  
  Hypervisor vendor:      KVM
  Virtualization type:    full
Caches (sum of all):      
  L1d:                    32 KiB (1 instance)
  L1i:                    32 KiB (1 instance)
  L2:                     256 KiB (1 instance)
  L3:                     55 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0,1
Vulnerabilities:          
  Gather data sampling:   Not affected
  Itlb multihit:          Not affected
  L1tf:                   Mitigation; PTE Inversion
  Mds:                    Vulnerable; SMT Host state unknown
  Meltdown:               Vulnerable
  Mmio stale data:        Vulnerable
  Reg file data sampling: Not affected
  Retbleed:               Vulnerable
  Spec rstack overflow:   Not affected
  Spec store bypass:      Vulnerable
  Spectre v1:             Vulnerable: __user pointer sanitization and usercopy barriers only; no swa
                          pgs barriers
  Spectre v2:             Vulnerable; IBPB: disabled; STIBP: disabled; PBRSB-eIBRS: Not affected; BH
                          I: Vulnerable (Syscall hardening enabled)
  Srbds:                  Not affected
  Tsx async abort:        Vulnerable
In [ ]:
# Memoria RAM
!free -h
               total        used        free      shared  buff/cache   available
Mem:            12Gi       2.3Gi       7.8Gi        15Mi       2.5Gi        10Gi
Swap:             0B          0B          0B
In [ ]:
# Sistema Operativo (OS) y Kernel
!uname -a
Linux 0c267e086795 6.1.85+ #1 SMP PREEMPT_DYNAMIC Thu Jun 27 21:05:47 UTC 2024 x86_64 x86_64 x86_64 GNU/Linux
In [ ]:
# GPU: No está disponible...
!nvidia-smi
/bin/bash: line 1: nvidia-smi: command not found
In [ ]:
# Disco Duro
!df -h
Filesystem      Size  Used Avail Use% Mounted on
overlay         108G   32G   77G  30% /
tmpfs            64M     0   64M   0% /dev
shm             5.8G     0  5.8G   0% /dev/shm
/dev/root       2.0G  1.2G  820M  59% /usr/sbin/docker-init
tmpfs           6.4G   15M  6.4G   1% /var/colab
/dev/sda1        80G   64G   17G  80% /kaggle/input
tmpfs           6.4G     0  6.4G   0% /proc/acpi
tmpfs           6.4G     0  6.4G   0% /proc/scsi
tmpfs           6.4G     0  6.4G   0% /sys/firmware
drive           108G   36G   73G  33% /content/drive
In [ ]:
# Versión de Python y Entorno
!python --version
import sys
print(sys.version)
Python 3.11.11
3.11.11 (main, Dec  4 2024, 08:55:07) [GCC 11.4.0]
In [ ]:
# Bibliotecas Instaladas
!pip list
Package                            Version
---------------------------------- -------------------
absl-py                            1.4.0
accelerate                         1.3.0
aiohappyeyeballs                   2.4.6
aiohttp                            3.11.12
aiosignal                          1.3.2
alabaster                          1.0.0
albucore                           0.0.23
albumentations                     2.0.4
ale-py                             0.10.2
altair                             5.5.0
annotated-types                    0.7.0
anyio                              3.7.1
argon2-cffi                        23.1.0
argon2-cffi-bindings               21.2.0
array_record                       0.6.0
arviz                              0.20.0
astropy                            7.0.1
astropy-iers-data                  0.2025.2.17.0.34.13
astunparse                         1.6.3
atpublic                           4.1.0
attrs                              25.1.0
audioread                          3.0.1
autograd                           1.7.0
babel                              2.17.0
backcall                           0.2.0
beautifulsoup4                     4.13.3
betterproto                        2.0.0b6
bigframes                          1.37.0
bigquery-magics                    0.6.0
bleach                             6.2.0
blinker                            1.9.0
blis                               0.7.11
blosc2                             3.1.1
bokeh                              3.6.3
Bottleneck                         1.4.2
bqplot                             0.12.44
branca                             0.8.1
CacheControl                       0.14.2
cachetools                         5.5.2
catalogue                          2.0.10
certifi                            2025.1.31
cffi                               1.17.1
chardet                            5.2.0
charset-normalizer                 3.4.1
chex                               0.1.88
clarabel                           0.10.0
click                              8.1.8
cloudpathlib                       0.20.0
cloudpickle                        3.1.1
cmake                              3.31.4
cmdstanpy                          1.2.5
colorcet                           3.1.0
colorlover                         0.3.0
colour                             0.1.5
community                          1.0.0b1
confection                         0.1.5
cons                               0.4.6
contourpy                          1.3.1
cramjam                            2.9.1
cryptography                       43.0.3
cuda-python                        12.6.0
cudf-cu12                          24.12.0
cudf-polars-cu12                   24.12.0
cufflinks                          0.17.3
cuml-cu12                          24.12.0
cupy-cuda12x                       13.3.0
cuvs-cu12                          24.12.0
cvxopt                             1.3.2
cvxpy                              1.6.1
cycler                             0.12.1
cyipopt                            1.5.0
cymem                              2.0.11
Cython                             3.0.12
dask                               2024.11.2
dask-cuda                          24.12.0
dask-cudf-cu12                     24.12.0
dask-expr                          1.1.19
datascience                        0.17.6
db-dtypes                          1.4.1
dbus-python                        1.2.18
debugpy                            1.8.0
decorator                          4.4.2
defusedxml                         0.7.1
Deprecated                         1.2.18
diffusers                          0.32.2
distributed                        2024.11.2
distributed-ucxx-cu12              0.41.0
distro                             1.9.0
dlib                               19.24.2
dm-tree                            0.1.9
docker-pycreds                     0.4.0
docstring_parser                   0.16
docutils                           0.21.2
dopamine_rl                        4.1.2
duckdb                             1.1.3
earthengine-api                    1.5.3
easydict                           1.13
editdistance                       0.8.1
eerepr                             0.1.1
einops                             0.8.1
en-core-web-sm                     3.7.1
entrypoints                        0.4
et_xmlfile                         2.0.0
etils                              1.12.0
etuples                            0.3.9
Farama-Notifications               0.0.4
fastai                             2.7.18
fastcore                           1.7.29
fastdownload                       0.0.7
fastjsonschema                     2.21.1
fastprogress                       1.0.3
fastrlock                          0.8.3
filelock                           3.17.0
firebase-admin                     6.6.0
Flask                              3.1.0
flatbuffers                        25.2.10
flax                               0.10.3
folium                             0.19.4
fonttools                          4.56.0
frozendict                         2.4.6
frozenlist                         1.5.0
fsspec                             2024.10.0
future                             1.0.0
gast                               0.6.0
gcsfs                              2024.10.0
GDAL                               3.6.4
gdown                              5.2.0
geemap                             0.35.1
gensim                             4.3.3
geocoder                           1.38.1
geographiclib                      2.0
geopandas                          1.0.1
geopy                              2.4.1
gin-config                         0.5.0
gitdb                              4.0.12
GitPython                          3.1.44
glob2                              0.7
google                             2.0.3
google-ai-generativelanguage       0.6.15
google-api-core                    2.24.1
google-api-python-client           2.160.0
google-auth                        2.27.0
google-auth-httplib2               0.2.0
google-auth-oauthlib               1.2.1
google-cloud-aiplatform            1.79.0
google-cloud-bigquery              3.29.0
google-cloud-bigquery-connection   1.18.1
google-cloud-bigquery-storage      2.28.0
google-cloud-bigtable              2.28.1
google-cloud-core                  2.4.2
google-cloud-dataproc              5.17.1
google-cloud-datastore             2.20.2
google-cloud-firestore             2.20.0
google-cloud-functions             1.19.0
google-cloud-iam                   2.18.1
google-cloud-language              2.16.0
google-cloud-pubsub                2.25.0
google-cloud-resource-manager      1.14.1
google-cloud-spanner               3.52.0
google-cloud-storage               2.19.0
google-cloud-translate             3.19.0
google-colab                       1.0.0
google-crc32c                      1.6.0
google-genai                       0.8.0
google-generativeai                0.8.4
google-pasta                       0.2.0
google-resumable-media             2.7.2
google-spark-connect               0.5.2
googleapis-common-protos           1.68.0
googledrivedownloader              1.1.0
graphviz                           0.20.3
greenlet                           3.1.1
grpc-google-iam-v1                 0.14.0
grpc-interceptor                   0.15.4
grpcio                             1.70.0
grpcio-status                      1.62.3
grpclib                            0.4.7
gspread                            6.1.4
gspread-dataframe                  4.0.0
gym                                0.25.2
gym-notices                        0.0.8
gymnasium                          1.0.0
h11                                0.14.0
h2                                 4.2.0
h5netcdf                           1.5.0
h5py                               3.12.1
hdbscan                            0.8.40
highspy                            1.9.0
holidays                           0.67
holoviews                          1.20.1
hpack                              4.1.0
html5lib                           1.1
httpcore                           1.0.7
httpimport                         1.4.0
httplib2                           0.22.0
httpx                              0.28.1
huggingface-hub                    0.28.1
humanize                           4.11.0
hyperframe                         6.1.0
hyperopt                           0.2.7
ibis-framework                     9.2.0
idna                               3.10
imageio                            2.37.0
imageio-ffmpeg                     0.6.0
imagesize                          1.4.1
imbalanced-learn                   0.13.0
imgaug                             0.4.0
immutabledict                      4.2.1
importlib_metadata                 8.6.1
importlib_resources                6.5.2
imutils                            0.5.4
inflect                            7.5.0
iniconfig                          2.0.0
intel-cmplr-lib-ur                 2025.0.4
intel-openmp                       2025.0.4
ipyevents                          2.0.2
ipyfilechooser                     0.6.0
ipykernel                          6.17.1
ipyleaflet                         0.19.2
ipyparallel                        8.8.0
ipython                            7.34.0
ipython-genutils                   0.2.0
ipython-sql                        0.5.0
ipytree                            0.2.2
ipywidgets                         7.7.1
itsdangerous                       2.2.0
jax                                0.4.33
jax-cuda12-pjrt                    0.4.33
jax-cuda12-plugin                  0.4.33
jaxlib                             0.4.33
jeepney                            0.7.1
jellyfish                          1.1.0
jieba                              0.42.1
Jinja2                             3.1.5
jiter                              0.8.2
joblib                             1.4.2
jsonpatch                          1.33
jsonpickle                         4.0.2
jsonpointer                        3.0.0
jsonschema                         4.23.0
jsonschema-specifications          2024.10.1
jupyter-client                     6.1.12
jupyter-console                    6.1.0
jupyter_core                       5.7.2
jupyter-leaflet                    0.19.2
jupyter-server                     1.24.0
jupyterlab_pygments                0.3.0
jupyterlab_widgets                 3.0.13
kaggle                             1.6.17
kagglehub                          0.3.9
keras                              3.8.0
keras-hub                          0.18.1
keras-nlp                          0.18.1
keyring                            23.5.0
kiwisolver                         1.4.8
langchain                          0.3.19
langchain-core                     0.3.37
langchain-text-splitters           0.3.6
langcodes                          3.5.0
langsmith                          0.3.9
language_data                      1.3.0
launchpadlib                       1.10.16
lazr.restfulclient                 0.14.4
lazr.uri                           1.0.6
lazy_loader                        0.4
libclang                           18.1.1
libcudf-cu12                       24.12.0
libkvikio-cu12                     24.12.1
librosa                            0.10.2.post1
libucx-cu12                        1.17.0.post1
libucxx-cu12                       0.41.0
lightgbm                           4.5.0
linkify-it-py                      2.0.3
llvmlite                           0.44.0
locket                             1.0.0
logical-unification                0.4.6
lxml                               5.3.1
marisa-trie                        1.2.1
Markdown                           3.7
markdown-it-py                     3.0.0
MarkupSafe                         3.0.2
matplotlib                         3.10.0
matplotlib-inline                  0.1.7
matplotlib-venn                    1.1.1
mdit-py-plugins                    0.4.2
mdurl                              0.1.2
miniKanren                         1.0.3
missingno                          0.5.2
mistune                            3.1.2
mizani                             0.13.1
mkl                                2025.0.1
ml-dtypes                          0.4.1
mlxtend                            0.23.4
more-itertools                     10.6.0
moviepy                            1.0.3
mpmath                             1.3.0
msgpack                            1.1.0
multidict                          6.1.0
multipledispatch                   1.0.0
multitasking                       0.0.11
murmurhash                         1.0.12
music21                            9.3.0
namex                              0.0.8
narwhals                           1.27.1
natsort                            8.4.0
nbclassic                          1.2.0
nbclient                           0.10.2
nbconvert                          7.16.6
nbformat                           5.10.4
ndindex                            1.9.2
nest-asyncio                       1.6.0
networkx                           3.4.2
nibabel                            5.3.2
nltk                               3.9.1
notebook                           6.5.5
notebook_shim                      0.2.4
numba                              0.61.0
numba-cuda                         0.0.17.1
numexpr                            2.10.2
numpy                              1.26.4
nvidia-cublas-cu12                 12.5.3.2
nvidia-cuda-cupti-cu12             12.5.82
nvidia-cuda-nvcc-cu12              12.5.82
nvidia-cuda-nvrtc-cu12             12.5.82
nvidia-cuda-runtime-cu12           12.5.82
nvidia-cudnn-cu12                  9.3.0.75
nvidia-cufft-cu12                  11.2.3.61
nvidia-curand-cu12                 10.3.6.82
nvidia-cusolver-cu12               11.6.3.83
nvidia-cusparse-cu12               12.5.1.3
nvidia-nccl-cu12                   2.21.5
nvidia-nvcomp-cu12                 4.1.0.6
nvidia-nvjitlink-cu12              12.5.82
nvidia-nvtx-cu12                   12.4.127
nvtx                               0.2.10
nx-cugraph-cu12                    24.12.0
oauth2client                       4.1.3
oauthlib                           3.2.2
openai                             1.61.1
opencv-contrib-python              4.11.0.86
opencv-python                      4.11.0.86
opencv-python-headless             4.11.0.86
openpyxl                           3.1.5
opentelemetry-api                  1.16.0
opentelemetry-sdk                  1.16.0
opentelemetry-semantic-conventions 0.37b0
opt_einsum                         3.4.0
optax                              0.2.4
optree                             0.14.0
orbax-checkpoint                   0.6.4
orjson                             3.10.15
osqp                               0.6.7.post3
packaging                          24.2
pandas                             2.2.2
pandas-datareader                  0.10.0
pandas-gbq                         0.27.0
pandas-stubs                       2.2.2.240909
pandocfilters                      1.5.1
panel                              1.6.1
param                              2.2.0
parso                              0.8.4
parsy                              2.1
partd                              1.4.2
pathlib                            1.0.1
patsy                              1.0.1
peewee                             3.17.9
peft                               0.14.0
pexpect                            4.9.0
pickleshare                        0.7.5
pillow                             11.1.0
pip                                24.1.2
platformdirs                       4.3.6
plotly                             5.24.1
plotnine                           0.14.5
pluggy                             1.5.0
ply                                3.11
polars                             1.14.0
pooch                              1.8.2
portpicker                         1.5.2
preshed                            3.0.9
prettytable                        3.14.0
proglog                            0.1.10
progressbar2                       4.5.0
prometheus_client                  0.21.1
promise                            2.3
prompt_toolkit                     3.0.50
propcache                          0.3.0
prophet                            1.1.6
proto-plus                         1.26.0
protobuf                           4.25.6
psutil                             5.9.5
psycopg2                           2.9.10
ptyprocess                         0.7.0
py-cpuinfo                         9.0.0
py4j                               0.10.9.7
pyarrow                            18.1.0
pyasn1                             0.6.1
pyasn1_modules                     0.4.1
pycocotools                        2.0.8
pycparser                          2.22
pydantic                           2.10.6
pydantic_core                      2.27.2
pydata-google-auth                 1.9.1
pydot                              3.0.4
pydotplus                          2.0.2
PyDrive                            1.3.1
PyDrive2                           1.21.3
pyerfa                             2.0.1.5
pygame                             2.6.1
pygit2                             1.17.0
Pygments                           2.18.0
PyGObject                          3.42.1
PyJWT                              2.10.1
pylibcudf-cu12                     24.12.0
pylibcugraph-cu12                  24.12.0
pylibraft-cu12                     24.12.0
pymc                               5.20.1
pymystem3                          0.2.0
pynndescent                        0.5.13
pynvjitlink-cu12                   0.5.0
pynvml                             11.4.1
pyogrio                            0.10.0
Pyomo                              6.8.2
PyOpenGL                           3.1.9
pyOpenSSL                          24.2.1
pyparsing                          3.2.1
pyperclip                          1.9.0
pyproj                             3.7.1
pyshp                              2.3.1
PySocks                            1.7.1
pyspark                            3.5.4
pytensor                           2.27.1
pytest                             8.3.4
python-apt                         0.0.0
python-box                         7.3.2
python-dateutil                    2.8.2
python-louvain                     0.16
python-slugify                     8.0.4
python-snappy                      0.7.3
python-utils                       3.9.1
pytz                               2025.1
pyviz_comms                        3.0.4
PyYAML                             6.0.2
pyzmq                              24.0.1
qdldl                              0.1.7.post5
raft-dask-cu12                     24.12.0
rapids-dask-dependency             24.12.0
ratelim                            0.1.6
referencing                        0.36.2
regex                              2024.11.6
requests                           2.32.3
requests-oauthlib                  2.0.0
requests-toolbelt                  1.0.0
requirements-parser                0.9.0
rich                               13.9.4
rmm-cu12                           24.12.1
rpds-py                            0.23.0
rpy2                               3.4.2
rsa                                4.9
safetensors                        0.5.2
scikit-image                       0.25.2
scikit-learn                       1.6.1
scipy                              1.13.1
scooby                             0.10.0
scs                                3.2.7.post2
seaborn                            0.13.2
SecretStorage                      3.3.1
Send2Trash                         1.8.3
sentence-transformers              3.4.1
sentencepiece                      0.2.0
sentry-sdk                         2.22.0
setproctitle                       1.3.4
setuptools                         75.1.0
shap                               0.46.0
shapely                            2.0.7
shellingham                        1.5.4
simple-parsing                     0.1.7
simsimd                            6.2.1
six                                1.17.0
sklearn-compat                     0.1.3
sklearn-pandas                     2.2.0
slicer                             0.0.8
smart-open                         7.1.0
smmap                              5.0.2
sniffio                            1.3.1
snowballstemmer                    2.2.0
sortedcontainers                   2.4.0
soundfile                          0.13.1
soupsieve                          2.6
soxr                               0.5.0.post1
spacy                              3.7.5
spacy-legacy                       3.0.12
spacy-loggers                      1.0.5
spanner-graph-notebook             1.1.1
Sphinx                             8.1.3
sphinxcontrib-applehelp            2.0.0
sphinxcontrib-devhelp              2.0.0
sphinxcontrib-htmlhelp             2.1.0
sphinxcontrib-jsmath               1.0.1
sphinxcontrib-qthelp               2.0.0
sphinxcontrib-serializinghtml      2.0.0
SQLAlchemy                         2.0.38
sqlglot                            25.6.1
sqlparse                           0.5.3
srsly                              2.5.1
stanio                             0.5.1
statsmodels                        0.14.4
stringzilla                        3.11.3
sympy                              1.13.1
tables                             3.10.2
tabulate                           0.9.0
tbb                                2022.0.0
tblib                              3.0.0
tcmlib                             1.2.0
tenacity                           9.0.0
tensorboard                        2.18.0
tensorboard-data-server            0.7.2
tensorflow                         2.18.0
tensorflow-datasets                4.9.7
tensorflow-hub                     0.16.1
tensorflow-io-gcs-filesystem       0.37.1
tensorflow-metadata                1.16.1
tensorflow-probability             0.25.0
tensorflow-text                    2.18.1
tensorstore                        0.1.72
termcolor                          2.5.0
terminado                          0.18.1
text-unidecode                     1.3
textblob                           0.19.0
tf_keras                           2.18.0
tf-slim                            1.1.0
thinc                              8.2.5
threadpoolctl                      3.5.0
tifffile                           2025.2.18
timm                               1.0.14
tinycss2                           1.4.0
tokenizers                         0.21.0
toml                               0.10.2
toolz                              0.12.1
torch                              2.5.1+cu124
torchaudio                         2.5.1+cu124
torchsummary                       1.5.1
torchvision                        0.20.1+cu124
tornado                            6.4.2
tqdm                               4.67.1
traitlets                          5.7.1
traittypes                         0.2.1
transformers                       4.48.3
treelite                           4.3.0
treescope                          0.1.9
triton                             3.1.0
tweepy                             4.15.0
typeguard                          4.4.2
typer                              0.15.1
types-pytz                         2025.1.0.20250204
types-setuptools                   75.8.0.20250225
typing_extensions                  4.12.2
tzdata                             2025.1
tzlocal                            5.3
uc-micro-py                        1.0.3
ucx-py-cu12                        0.41.0
ucxx-cu12                          0.41.0
umap-learn                         0.5.7
umf                                0.9.1
uritemplate                        4.1.1
urllib3                            2.3.0
vega-datasets                      0.9.0
wadllib                            1.3.6
wandb                              0.19.7
wasabi                             1.1.3
wcwidth                            0.2.13
weasel                             0.4.1
webcolors                          24.11.1
webencodings                       0.5.1
websocket-client                   1.8.0
websockets                         14.2
Werkzeug                           3.1.3
wheel                              0.45.1
widgetsnbextension                 3.6.10
wordcloud                          1.9.4
wrapt                              1.17.2
xarray                             2025.1.2
xarray-einstats                    0.8.0
xgboost                            2.1.4
xlrd                               2.0.1
xyzservices                        2025.1.0
yarl                               1.18.3
yellowbrick                        1.5
yfinance                           0.2.54
zict                               3.0.0
zipp                               3.21.0
zstandard                          0.23.0

10. Ética de la Investigación¶

Integridad Científica¶

Reporte de Fallos y Datos Incompletos¶

  • Datos descartados:
    Solo se eliminaron réplicas con errores críticos (e.g., valores NULL).
    • Ejemplo: $2000$ réplicas de fuerza bruta ($FB$) en $n>14$ fueron descartadas por timeout ($>24h$) con el marcador skip_large_for_exponential en cada uno de los dataset ($2$).
    • Justificación: Se constataron los valores de ($FB$) en la columa estatus con status = skipped_due_to_large_n, de lo contrario eran ok.

Análisis de Varianzas y Tukey HSD¶

  • Prueba Post-Hoc (ANOVA + Tukey):
    $$ \text{Intervalo de Confianza (95 %)}_{DP vs FB} = [\mu_{DP} - 1.96\sigma/\sqrt{n}, \mu_{DP} + 1.96\sigma/\sqrt{n}] $$
    • Resultado:
      • $p < 0.001$ para todas las comparaciones DP vs FB ($\Delta \mu = 96.8\%$).
      • Efecto de Librería:
        Tracemalloc introdujo un overhead del $12.7\%$ en tiempo vs psutil ($t=4.3$, $p=0.022$).

Transparencia en Mediciones de Memoria¶

Librería Ventaja Limitación Impacto en FB (n=14)
Psutil Mide RAM física total Incluye memoria de librerías externas $\mu = 0.67$ MB
Tracemalloc Rastrea asignaciones específicas en heap Ignora memoria de la pila (stack) $\mu = 0.84$ MB
  • Conclusión Metodológica:

    "La discrepancia $\Delta \mu = 25\%$ entre librerías exige reportar ambas métricas para auditorías técnicas".


Uso Responsable de Recursos y Costo Energético¶

¿Qué es $E_{\text{total}}$?¶

En nuestro proyecto, $E_{\text{total}}$ representa la energía total consumida durante la ejecución de todas las réplicas de nuestros experimentos. Es decir, es la suma del consumo energético asociado tanto a la CPU como a la RAM durante cada réplica, expresado en kilovatios-hora $[\text{kWh}]$

La fórmula utilizada es:

$$ E_{\text{total}} = \sum_{i=1}^{R} \left( \underbrace{P_{\text{CPU}} \cdot t_i}_{\text{Consumo CPU}} + \underbrace{P_{\text{RAM}} \cdot m_i}_{\text{Consumo RAM}} \right) \quad [\text{kWh}] $$

Donde:

  • $P_{\text{CPU}}$ es la potencia consumida por la CPU (en nuestro caso, $0.15$ kW, basado en el TDP del Intel Xeon E5-2680v4).
  • $t_i$ es el tiempo de ejecución (en horas) de la réplica $i$.
  • $P_{\text{RAM}}$ es la potencia consumida por la RAM (por ejemplo, $0.05$ kW por cada 256 GB, según estándares DDR4).
  • $m_i$ representa el factor de memoria utilizado en la réplica $i$ (en unidades equivalentes a 256 GB, si se utiliza la misma escala).
  • $R$ es el número total de réplicas (50 en nuestro caso).

Parámetros y Sustitución:¶

Parámetro Valor Fuente/Criterio
$P_{\text{CPU}}$ $0.15$ kW (150 W) TDP oficial del Intel Xeon E5-2680v4 (ARK Intel)
$P_{\text{RAM}}$ $0.05$ kW (50 W) por 256 GB Consumo estándar DDR4 (JEDEC)
$t_{\text{total}}$ $35$ horas Sumatoria de todas las réplicas (50 ejecuciones × tiempo promedio por réplica)

| $R$ | $50$ réplicas | Decisión estadística para poder predictivo (error < 5%)

Con un tiempo total acumulado de $35$ horas para 50 réplicas, se llegó a que:

Cálculo:
$$ E_{\text{total}} = (0.15\ \text{kW} \times 35\ \text{h}) + (0.05\ \text{kW} \times 35 \text{h}) = 7\ \text{kWh} $$

$$ E_{\text{total}} = 7 \; \text{kWh} $$

Tarifa Energética en Diferentes Regiones¶

A continuación, se muestran ejemplos de tarifas aproximadas en otras regiones:

  • Colombia:
    Las tarifas industriales en Colombia suelen estar en el rango de $0.08$ USD/kWh.
    Costo estimado:
    $$ \text{Costo} = 7 \; \text{kWh} \times 0.08 \; \text{USD/kWh} \approx 0.56 \; \text{USD} \approx $ 2.400 \text{ COP} $$

  • Estados Unidos:
    Dependiendo de la región, las tarifas industriales en EE. UU. pueden oscilar entre $0.07$ y $0.10$ USD/kWh.
    Si asumimos un valor de $0.09$ USD/kWh:
    $$ \text{Costo} = 7 \; \text{kWh} \times 0.09 \; \text{USD/kWh} \approx 0.63 \; \text{USD} $$

  • Europa (por ejemplo, Alemania):
    En algunos países europeos, las tarifas industriales pueden ser más elevadas, por ejemplo, alrededor de $0.27$ USD/kWh (aproximadamente 0.25 €/kWh).
    Costo estimado:
    $$ \text{Costo} = 7 \; \text{kWh} \times 0.27 \; \text{USD/kWh} \approx 1.89 \; \text{USD} $$


Aclaración¶

Estos valores son estimados. La mayoría de los experimentos se realizaron en diferentes entornos de Google Colab y en una máquina física de un colega (aunque en pocas horas). Por ello, estos cálculos deben considerarse aproximados y sirven para dar una idea del impacto energético y económico del proyecto acádemico, para la materia: Análisis y diseño de algoritmos.


Transparencia y Auditoría¶

Para garantizar la reproducibilidad y la transparencia de la investigación, se ha preparado un dataset público que documenta cada experimento realizado.


11. Referencias bibliográficas¶

  1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th ed.). MIT Press.

  2. Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680. https://doi.org/10.1126/science.220.4598.671

  3. Mitchell, M. (1998). An introduction to genetic algorithms. MIT Press.

Autores:¶

  1. $\text{Juanda Ramírez}$. jramirezor@unal.edu.co

  1. $\text{Hervin R.}$ herdrodriguezcas@unal.edu.co

In [77]:
# Primero exportar a HTML
!jupyter nbconvert --to html '/content/drive/MyDrive/UNAL/Semestre IV/Análisis y diseño de Algoritmos/Proyecto/Corrección - Alquiler de Canoas.ipynb'

# Instalar wkhtmltopdf para la conversión de HTML a PDF
!apt-get install -y wkhtmltopdf

# Convertir el HTML a PDF
!wkhtmltopdf '/content/drive/MyDrive/UNAL/Semestre IV/Análisis y diseño de Algoritmos/Proyecto/Corrección - Alquiler de Canoas.html' '/content/drive/MyDrive/UNAL/Semestre IV/Análisis y diseño de Algoritmos/Proyecto/Corrección - Alquiler de Canoas.pdf'
[NbConvertApp] Converting notebook /content/drive/MyDrive/UNAL/Semestre IV/Análisis y diseño de Algoritmos/Proyecto/Corrección - Alquiler de Canoas.ipynb to html
[NbConvertApp] WARNING | Alternative text is missing on 27 image(s).
[NbConvertApp] Writing 4258087 bytes to /content/drive/MyDrive/UNAL/Semestre IV/Análisis y diseño de Algoritmos/Proyecto/Corrección - Alquiler de Canoas.html
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
wkhtmltopdf is already the newest version (0.12.6-2).
0 upgraded, 0 newly installed, 0 to remove and 31 not upgraded.
QStandardPaths: XDG_RUNTIME_DIR not set, defaulting to '/tmp/runtime-root'
Loading page (1/2)
Printing pages (2/2)                                               
Done